Combinatorics

Need to know how many different five-card hands you can pick from a pack of 32 cards? That is exactly the kind of problem combinatorics deals with. There are two basic counting rules – the addition rule and the product rule. All other methods are just extensions of these two principles.

The addition rule

The addition rule is very simple. It says that if we have sets A, B with no element in common, then the number of ways to choose one element from the union A ∪ B is |A| + |B|, that is, the sum of the sizes of the sets.

Let’s start with an easy example. We have 6 red balls and 8 blue balls, and we tip them all into one bag. How many different outcomes are there if we pick one ball? Let’s call the set of red balls A and the set of blue balls B. These sets are disjoint, which means that no ball belongs to both. We want to pick one ball, so there are |A| + |B| = 6 + 8 = 14 possibilities. That’s all there is to it.

The product rule

Again we have two sets, W and M. The set W contains three women and the set M four men. Now we ask: how many different (man, woman) pairs can we make from these sets? What we are doing is this: we always take one woman and match her with a man. To count all the pairs, we take one woman, Amelia, and match her with each of the men in turn. That gives 4 different pairs, because there are 4 different men to choose from. We do the same for the remaining two women, and each of them also gives 4 pairs. That’s everything, so there are 4 + 4 + 4 = 12 pairs in total.

What have we actually done? We multiplied the sizes of the two sets. There were 3 women and 4 men, so the total number of pairs is 3 · 4 = 12. Hence the name, the product rule. If we form pairs from two sets, we simply multiply the number of elements in one set by the number of elements in the other.

You can also check that this really works. Below are all the pairs we can make from 3 women and 4 men. Each row shows the options for one of the women and each column the options for one of the men. So there are three rows and four columns, giving rows · columns possibilities in total.

$$\begin{array}{rcl}& & (W_1,M_1),(W_1,M_2),(W_1,M_3),(W_1,M_4),\\ & & (W_2,M_1),(W_2,M_2),(W_2,M_3),(W_2,M_4),\\ & & (W_3,M_1),(W_3,M_2),(W_3,M_3),(W_3,M_4)\end{array}$$

Worked examples

1. How many different two-digit numbers are there? What does a two-digit number look like? The first place holds one of the digits 1, …, 9, while the second place can also hold zero: 0, …, 9. So the first set has 9 digits and the second has 10. Using the product rule, we get the final result: 9 · 10 = 90.

• How many different three-digit numbers are there in which no digit may appear twice? Again, the first place can hold nine digits, because a number cannot start with zero. The second place can hold any digit, including zero, but it cannot be the digit used in the first place, so we subtract one from the ten possible digits (for example, if our three-digit number starts with a 4, the 4 clearly cannot appear in the second place, because it would then occur twice in the number). The third place can again hold any digit except the ones in the first and second places, for the same reason. If the first digit is 4 and the second is 7, we can fill the third place with one digit from {0, …, 9} ∖ {4, 7}. From the ten digits we must subtract two. Now we just multiply: 9 · 9 · 8 = 648. So there are 648 such numbers.
• We roll a standard dice twice in a row. How many different outcomes can we get? The first roll can give 6 different results. So can the second, so the total number of possibilities is 6 · 6 = 36.
• We roll a dice twice in a row. How many different outcomes can we get if the first roll was an even number? The first roll was even, that is, one of 2, 4, 6, which gives 3 possibilities. The second roll can be any number, so altogether we have 3 · 6 = 18 possibilities.