45
Elements of combinatorics
Textbook, p. 206
GoalFirst ideas of combinatorics: the addition rule and counting ways to arrange items.
New words
combinatorics · kombinatorikaaddition rule · qo‘shish qoidasiway (method) · usultree diagram · daraxt sxemasi
Explanation
Combinatorics answers the question “how many ways are there?”. The addition rule: if we can choose from group A in m ways or from group B in n ways, and the choice is “either from A or from B”, the total is m + n ways. For example if basket 1 has 20 apples and basket 2 has 30, we can take one apple in 20 + 30 = 50 ways. To count all possible arrangements in an orderly way we use a tree diagram: the letters A, B, C can be put in a row in 6 ways: ABC, ACB, BAC, BCA, CAB, CBA.
Worked examples
A shop has 4 kinds of pens and 3 kinds of pencils. Choosing one item (a pen or a pencil) can be done in 4 + 3 = 7 ways.
Putting A, B, C in a row: 3 choices for the first place, 2 for the second and 1 for the last; 3 · 2 · 1 = 6 ways in all.
Class activity
“Line-up”: three pupils stand side by side. The class arranges them in all possible orders and counts the ways, then compares with a tree diagram.
Practice
1
Basket 1 has 20 apples and basket 2 has 30. In how many ways can one apple be taken?
50
2
A shop has 4 kinds of pens and 3 kinds of pencils. In how many ways can one item be chosen?
7
3
In how many ways can the letters A, B, C be put in a row?
6
4
Why do we add the numbers of ways here instead of multiplying?
The choice is “either-or”: only one item is taken, so the ways from the different groups add up.