Combinations

25 min

When order does not matter

In the last lesson the cooperative of 10 elected a president, a secretary and a treasurer: ${}^{10}P_{3} = 720$ results, because Keza as president and Mugisha as secretary differs from the reverse. Now suppose the cooperative simply sends three members to a training in Kigali. Keza, Mugisha and Gatete form the same delegation whatever order they are picked in. Each delegation of 3 was counted $3! = 6$ times among the 720 ordered results, so there are $\frac{720}{6} = 120$ delegations.

Definition

A combination is a selection of objects in which order does not matter. The number of combinations of $r$ objects chosen from $n$ different objects is

{}^{n}C_{r} = \binom{n}{r} = \frac{n!}{r!\,(n-r)!}

read " $n$ choose $r$ ". Since every selection of $r$ objects can be ordered in $r!$ ways, ${}^{n}P_{r} = {}^{n}C_{r} \times r!$ .

Example: ${}^{10}C_{3} = \frac{10!}{3!\,7!} = \frac{10 \times 9 \times 8}{6} = 120$ .

Properties

${}^{n}C_{0} = {}^{n}C_{n} = 1$ : there is one way to choose nothing, and one way to choose everything.
${}^{n}C_{r} = {}^{n}C_{n-r}$ : choosing the $r$ objects to take is the same as choosing the $n - r$ to leave. For example ${}^{12}C_{10} = {}^{12}C_{2} = 66$ .
${}^{n}C_{r} + {}^{n}C_{r+1} = {}^{n+1}C_{r+1}$ (Pascal's rule), which builds Pascal's triangle.

Question asks…	Order matters?	Use
a president, secretary and treasurer	yes: different posts	${}^{n}P_{r}$
a delegation, a team, a committee, a hand of cards	no	${}^{n}C_{r}$
a PIN, a word, a number, a queue	yes	${}^{n}P_{r}$ or the product rule

Handshakes and lines

If 5 people each shake hands once with every other, each handshake is a pair of people, and the pair (Keza, Mugisha) is the same as (Mugisha, Keza). So there are ${}^{5}C_{2} = 10$ handshakes, one for each line in the diagram.

Worked example

Worked example 1. A committee of 5 is chosen from 7 men and 6 women. How many committees contain (a) exactly 2 women; (b) at least 2 women?

(a) Choose the women and the men separately, then multiply (two stages):

{}^{6}C_{2} \times {}^{7}C_{3} = 15 \times 35 = 525

(b) "At least 2" means 2, 3, 4 or 5 women. It is quicker to subtract the unwanted cases from the total:

{}^{13}C_{5} - \underbrace{{}^{7}C_{5}}_{\text{0 women}} - \underbrace{{}^{6}C_{1} \times {}^{7}C_{4}}_{\text{1 woman}} = 1287 - 21 - 210 = 1056

Check by adding the wanted cases: $525 + 20 \times 21 + 15 \times 7 + 6 \times 1 = 525 + 420 + 105 + 6 = 1056$ . Both methods agree.

Worked example

Worked example 2. Eight points lie on a circle. How many (a) chords; (b) triangles can be drawn with vertices at these points?

(a) A chord is fixed by 2 points: ${}^{8}C_{2} = 28$ .

(b) A triangle is fixed by 3 points (no three points on a circle are in a line): ${}^{8}C_{3} = 56$ .

Worked example

Worked example 3: choose, then arrange. From 9 players a coach picks 4 for a relay team and then decides the running order. In how many ways?

Choose: ${}^{9}C_{4} = 126$ . Arrange the 4: $4! = 24$ . Total $126 \times 24 = 3024$ , which equals ${}^{9}P_{4}$ , as it must.

Khan Academy derives the combination formula by starting from permutations and dividing out the orders of the people chosen, the same reasoning as the delegation above.

Warning

Adding instead of multiplying across groups. "2 women and 3 men" is ${}^{6}C_{2} \times {}^{7}C_{3}$ , not ${}^{6}C_{2} + {}^{7}C_{3}$ : each choice of women goes with each choice of men. And "at least" problems are usually quicker as "total minus the cases you do not want".

Tip

Ask: "If I swap two of the chosen objects, do I get a different result?" If yes, order matters (permutation). If no, it is a combination.

✦

Practice

Evaluate ${}^{9}C_{3}$ and ${}^{20}C_{18}$ .
In how many ways can a reading club choose 4 novels from a list of 11?
Twelve teams each play every other team once. How many matches are played?
A team of 6 is chosen from 8 boys and 5 girls. How many teams have exactly 4 boys?
From the same 8 boys and 5 girls, how many teams of 6 have at least one girl?
Solve ${}^{n}C_{2} = 45$ .
Explain, without calculating, why ${}^{15}C_{4} = {}^{15}C_{11}$ .

Show answersHide answers

$\frac{9 \times 8 \times 7}{6} = 84$ ; ${}^{20}C_{2} = \frac{20 \times 19}{2} = 190$ .
${}^{11}C_{4} = 330$ .
${}^{12}C_{2} = 66$ .
${}^{8}C_{4} \times {}^{5}C_{2} = 70 \times 10 = 700$ .
Total ${}^{13}C_{6} = 1716$ ; no girl ${}^{8}C_{6} = 28$ ; at least one girl $1716 - 28 = 1688$ .
$\frac{n(n-1)}{2} = 45$ , so $n (n - 1) = 90$ and $n = 10$ .
Choosing 4 of the 15 to take is the same as choosing the 11 to leave behind, so the two numbers count the same selections.

Important

${}^{n}C_{r} = \frac{n!}{r!\,(n-r)!}$ counts selections; ${}^{n}P_{r} = {}^{n}C_{r} \times r!$ counts arrangements. "And" between groups multiplies; "at least" is often total minus the rest.

1When order does not matter

2Properties

3Handshakes and lines

When order does not matter

Properties

Handshakes and lines