Combinations
Martin McBride, 2021-11-04
Tags combinations
Categories statistics probability
Combinations are similar to permutations. The difference is that, with combinations, the order of the items doesn't matter.
Example of combinations
One example of combinations is the National Lottery. The machine has 59 balls, numbered 1 to 59. In the game, 6 balls are chosen.
It doesn't matter which order the balls are drawn, if the 6 numbers match your ticket you will win. If the numbers are drawn in the order (10, 17 45, 23, 52, 36) the result is exactly the same as the numbers being drawn in the order (45, 52, 17, 36, 10, 23). The two situations are considered identical in terms of the final result.
In other words
- (10, 17 45, 23, 52, 36) and (45, 52, 17, 36, 10, 23) are identical combinations, because each set contains the same numbers.
- But they are different permutations, because the numbers are in a different order.
Calculating the number of combinations
In the article on permutations, we used an example of 5 different coloured counters - red, yellow, green, blue, and black.
If we pick 3 of the counters at random, how many possible combinations are there?
We know that the number of permutations of 3 elements from 5 is:
$$ \frac {n!}{(n-r)!} = \frac {5!}{2!} = 60 $$
However, some of these different permutations are the same combination. For example the permutations RGB, GRB and BGR are all the same combination of a red, a green, and a blue counter.
In fact, for every combination of 3 counters, there are 3 factorial permutations. So to obtain the current number of combinations we must divide the number of permutations by 3 factorial (in more generally r factorial):
$$ \frac {n!}{r!(n-r)!} = \frac {5!}{3!.2!} = 10 $$
Symmetry
The number of combinations of r items from n is equal to the number of combinations of (n-r) items from n.
This can be seen intuitively, as follows. Using the previous example, whenever we take a combination of 3 counters, we leave 2 counters behind. For each unique combination of 3 counters, there is a corresponding unique combination of the remaining 2 counters. So the number of combinations of 3 counters from 5 is equal to the number of combinations of 2 counters from 5.
Alternatively, we can show this from the equation:
$$ \frac {n!}{r!(n-r)!} $$
If we replace r with (n - r) we get:
$$ \frac {n!}{(n-r)!(n-(n-r))!} = \frac {n!}{(n-r)!r!} = \frac {n!}{r!(n-r)!} $$
Combinations with repeats
In the previous example, we were selecting r objects from a set of n unique objects. No object can appear more than once in the combination. The same Lottery ball can't be drawn twice.
In this section, we will consider the case where repeats are allowed. For example, throwing a dice 10 times, and writing down the result each time. Clearly, the same number can appear more than once in the result. How many combinations are possible?
In this case, n is 6 because there are 6 possible scores. r is 10 because we throw the dice 10 times.
The solution to this requires us to look at the problem in a slightly different way. We could create a table of the number of times each score appears. For example:
| Score | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Count | 2 | 1 | 1 | 3 | 2 | 1 |
This table shows that, when we threw the dice 10 times, it came up as 1 twice, it never came up as 2, it came up as 3 twice, and so on. The total of all the counts must be 10 because we threw the dice 10 times.
Here is another way of representing the table:
| Score | 1 | 2 | 3 | 4 | 5 | 6 |
|---|---|---|---|---|---|---|
| Count | XX | X | X | XXX | XX | X |
The number of 'X' characters represent the number of throws with that particular score.
We can avoid the table altogether by using a different character ':' to separate the X characters.
XX:X:X:XXX:XX:X
This set of characters contains 10 'X' characters (each representing a throw of the dice). It contains 5 ':' characters to divide the 'X' characters into 6 groups. In terms of n and r:
- The number of 'X' characters is r.
- There number of ':' characters is n - 1.
The key thing here is that every possible combination of dice scores is represented by a unique permutation of the characters. In fact, there is a one-to-one correspondence.
The string 'XX:X:X:XXX:XX:X' represents the scores in order 1 to 6. It doesn't depend on the order of the scores, so it represents a unique combination.
This means that the number of combinations of dice throws is the same as the number of permutations of 10 'X' and 5 ':' characters. In the section on permutations we saw that the formula for the number of permutations of a binary set is:
$$ \frac {n!}{c!(n-c)!} $$
In this case, the total number of 'X' and ':' characters is n + r - 1. Substituting this for n in the formula above gives a formula for the number of combinations of r objects from a set of n unique objects, with repeats allowed as:
$$ \frac {(n-r-1)!}{r!(n-1)!} $$
