Combinations

We use combinations when we choose a certain number of objects from a set and the order in which we choose them does not matter. A typical example is a lottery – the bag holds 49 numbers and we draw 6 of them, and it doesn’t matter in which order they come out.

Deriving the formula

Wheel of fortune

Take a set M, for example M = {a, b, c, d, e}. Then a k-element combination is a subset K ⊆ M that contains exactly k elements. Since K is a set, order obviously doesn’t matter. So a three-element combination of the set M could be {a, b, d} or {b, c, d}.

The difference from k-permutations is that for k-permutations order mattered, so (a, b, e) and (e, b, a) are different k-permutations, but they are the same combination, because (a, b, e) and (e, b, a) contain the same elements; for combinations we don’t care that they are in a different order.

But we can use k-permutations to get a formula for the number of different combinations. We know that the number of k-element k-permutations from a set of n elements is

$P (n, k) = \frac{n!}{(n - k)!} .$

So if we counted all the three-element k-permutations of the set M = {a, b, c, d, e}, we would get P(5, 3) = 60 different arrangements. However, for each triple we would also have all of its permutations. That is, we would have the triple abc, but also the triples acb, bac, bca, cab and cba. These are six different arrangements, but just one combination, because they all have the same elements.

So if we have a triple, how many different permutations of it are there? Exactly 3!. In other words, there are exactly 3! times as many three-element k-permutations as three-element combinations. Instead of counting one combination, we are counting 3! arrangements, one for each permutation of the triple. So if we divide the number of k-permutations by 3!, we get the number of combinations.

We can generalise this: if we look for the number of all different k-element combinations from a set of size n, this number, which we write as $(\binom{n}{k})$ (read “n choose k”), is

$(\binom{n}{k}) = \frac{P (n, k)}{k!},$

that is, the number of k-permutations divided by k!, which is the number of permutations of each k-tuple. We can rewrite the formula by expanding the formula for k-permutations:

$(\binom{n}{k}) = \frac{P (n, k)}{k!} = \frac{n!}{(n - k)!} \cdot \frac{1}{k!} = \frac{n!}{(n - k)! \cdot k!} .$

Example: the number of two-element combinations from the set {a, b, c} is

$(\binom{3}{2}) = \frac{3!}{1! \cdot 2!} = 3$

and these are the combinations: {a, b}, {a, c} and {b, c}. For three-element combinations from the original set M = {a, b, c, d, e} we would get

$(\binom{5}{3}) = \frac{5!}{(5 - 3)! \cdot 3!} = 10$

and these are the combinations: {a, b, c}, {a, b, d}, {a, b, e}, {a, c, d}, {a, c, e}, {a, d, e}, {b, c, d}, {b, c, e}, {b, d, e}, {c, d, e}.

The binomial coefficient

The number of combinations is usually written with the so-called binomial coefficient (other notations such as C(n, k) exist, and on a calculator the button is nCr). The binomial coefficient has this form

$(\binom{n}{k})$

It is a sort of fraction without a fraction bar (which you will write out of habit anyway), but with brackets (these are not optional, they have to be there). We read the binomial coefficient as “n choose k”. Its value is the number of k-element combinations from n elements.

$(\binom{n}{k}) = \frac{n!}{(n - k)! \cdot k!}$

So if we have a set of 5 elements and choose groups of four from it, the total number of them is

$(\binom{5}{4}) = \frac{5!}{1! \cdot 4!} = 5.$

Basic relations

For the binomial coefficient and n ∈ ℤ⁺ we have:

$\begin{array}{rcl} (\binom{n}{0}) = (\binom{n}{n}) = (\binom{0}{0}) & = & 1 \\ (\binom{n}{1}) & = & n \end{array}$

Also, for n, k ∈ ℕ₀ and k ≤ n we have

$\begin{array}{rcl} (\binom{n}{n - k}) & = & (\binom{n}{k}) . \end{array}$

And for n, k ∈ ℕ₀ and k < n we have

$\begin{array}{rcl} (\binom{n}{k}) + (\binom{n}{k + 1}) & = & (\binom{n + 1}{k + 1}) . \end{array}$

Calculator

The calculator below works out the binomial coefficient n choose k.

Worked examples

Let’s start with the lottery mentioned above. Here 6 balls are drawn from a bag containing 49 balls. How many different draws are possible?

First of all – does the order in which the numbers are drawn matter? No, we only pick the numbers, not their order. So we use combinations. There are 49 balls in total and we draw 6 of them, which gives the binomial coefficient

$(\binom{49}{6}) = \frac{49!}{(49 - 6)! \cdot 6!} = \frac{49!}{43! \cdot 6!} = 13,983,816$

There are 13,983,816 possible draws. Incidentally, this gives us the probability of winning with a single ticket, 1/13,983,816, which is 0.00000715112%.
Oliver is at a party where there are 13 classmates he would like to chat to. He knows he has time to talk to 4 different people during the evening. How many different groups of four can Oliver choose from?

This is again a simple combinations problem: the order doesn’t matter, because it makes no difference whom he talks to first and whom last. So we have a set of 13 people, from which we always choose 4. This leads to the binomial coefficient

$(\binom{13}{4}) = 715.$
You have a group of fifty people, half men and half women. How many different groups of three people are there if a group must not consist of one sex only (that is, a group must not contain three men or three women)?

This is a slightly harder combinations problem. If we exclude single-sex groups, only two ways of composing a group remain – two men and one woman, or one man and two women – and the number of combinations of the first kind (two men and one woman) is the same as the number of the second kind. So it is enough to work out the number of combinations of the first kind and then multiply it by two. Now it is easy again. We find the number of different pairs of men, which is 25 choose 2, and multiply it by the number of ways to choose one woman (that is 25, see the basic relations above, specifically the second line). Finally we multiply this result by two and we have the answer.

$2 \cdot (\binom{25}{2}) \cdot (\binom{25}{1}) = 15000.$
A box contains 15 items, 4 of which are faulty. In how many ways can 6 items be chosen so that
- none of them is faulty? Here we choose 6 items from the 15 − 4 = 11 items that are not faulty. This gives the binomial coefficient
  
  $(\binom{11}{6}) = 462.$
- exactly one item is faulty? So we choose a set that contains 5 working items and 1 faulty one. There are 11 working items and 4 faulty ones. Using the product rule, we get the result:
  
  $(\binom{11}{5}) \cdot (\binom{4}{1}) = 1848$
- at most one item is faulty? We use the previous results. We know that there are 462 ways to choose exactly 6 working items and 1848 ways to choose five working items and one faulty item. Using the addition rule, we add these results and get what we want, that is, at most one faulty item (= either no faulty item or exactly one). The result is: 462 + 1848 = 2310.

Chapters: Combinatorics, Arrangements (k-permutations), Permutations, Combinations, Arrangements with repetition, Combinations with repetition, How many different PINs are there?

« Previous: Permutations

Next: Arrangements with repetition »