Combinatorics
Kapitoly: Combinatorics, Variations, Permutation, Combination, Variations with repetition, Combination with repetition, How many different PINs are there, Calculator.
Need to know how many different fives of cards you can pick from a deck of 32 cards? That's exactly the type of problem combinatorics solves. There are two basic combinatorial rules - sum and product. All other procedures are just extensions of these basic principles.
The combinatorial rule of sum
The sum rule is very simple - it tells us that if we have sets A, B, which have no common element, then the number of all possible ways of selecting one element from the union A ∪ B is equal to |A| + |B|, i.e. the sum of the sizes of the sets.
Let's start with a lightweight example. We have 6 red balls and 8 blue balls. Let's dump these balls into a single pool. How many possibilities do we have in total if we draw one ball? At the beginning we had a set of red balls, let's denote as the set A, then a set of blue balls, let's denote B. These sets are disjunctive, i.e., they have no same ball. We want to draw one ball, so we have a total of |A| + |B| = 6 + 8 = 14 possibilities. That's it.
The combinatorial product rule
We again have two sets, Z and M. The set Z contains three women and the set M contains four men. Now we ask, how many different pairs of muž—žena can we make from these sets? What we're trying to do is always take one woman and assign her a man. We count the number of all pairs as follows: we take one woman, Kate, and assign all the men to her in turn. This gives us 4 different pairs, because we can assign 4 different men to her. We do the same for the other two women, they also make 4 more pairs each time. And that's it, we have a total of 4 + 4 + 4 = 12 pairs.
What have we actually done? We multiplied the size of the two sets. We had 3 ladies and 4 gentlemen, so the total number of pairs is 3 · 4 = 12. Hence the combinatorial product rule. So if we have any two sets from which we form pairs, we simply multiply the number of elements of one set by the number of elements of the other set.
You can see below that this actually holds. Following are all the ways we can arrange 3 women and 4 men into pairs. Each row represents the possibilities for one of the women and each column represents the possibilities for one of the men. So we have three rows and four columns, for a total of řádky · sloupce possibilities.
$$\begin{eqnarray} &&[Z_1, M_1], [Z_1, M_2], [Z_1, M_3], [Z_1, M_4], \\ &&[Z_2, M_1], [Z_2, M_2], [Z_2, M_3], [Z_2, M_4], \\ &&[Z_3, M_1], [Z_3, M_2], [Z_3, M_3], [Z_3, M_4] \end{eqnarray}$$
Examples solved
- How many different double-digit numbers are there? What does such a two-digit number look like? One of the digits occurs in the first place 1, …, 9, while the second place may have an extra zero: 0, …, 9. So we have 9 digits in the first set, and 10 in the second. We apply the combinatorial product rule to get the final result: 9 · 10 = 90.
- How many different three-digit numbers are there where no digit can occur twice? Nine digits can be in the first place again, but the number cannot start with zero. In the second position there can be all digits, including zero, but there cannot be a digit occurring in the first position, so we subtract one from the number of ten possible digits (for example, if our three-digit number just starts with four, it is clear that four cannot occur in the second position anymore, because it would be twice in the whole number). Again, all digits can be in the third position, but the digit that is in the first or second position cannot be there. The reason is again the same. If the digit 4 is in the first place and the digit 7 is in the second place, we can add one digit from {0, …, 9} ∖ {4, 7} to the third place. Now we just multiply by 9 · 9 · 8 = 648. The total number of combinations is 648.
- Roll the dice twice in a row. How many different results can we get? On the first roll, we can get 6 different results on the dice. On the second roll, the total number of possibilities is 6 · 6 = 36.
- Roll the dice twice in a row. How many different outcomes can we get if we roll an even number on the first roll? In the first roll, an even number was rolled, i.e. one of the numbers 2, 4, 6 was rolled, giving a total of 3 possibilities. In the second roll, any number can be rolled, so we have a total of 3 · 6 = 18 possibilities.