Combinations

AS · S1 · 13 min

A combination is a selection in which the order does not matter: choosing a committee, a hand of cards, a team, a handful of sweets from a bag. Combinations are counted with ${}^{n}C_{r}$ , the same number that appears in the binomial expansion and in the binomial distribution. On Paper 5 they appear in the permutations and combinations question (committees with conditions, "at least one", particular people included or excluded, selections followed by arrangements) and in probability questions where items are drawn at random without replacement.

Permutation or combination?

The single most important decision in any counting question is whether order matters.

Situation	Order matters?	Count with
Arranging people in a queue	Yes	permutations
Awarding gold, silver, bronze	Yes	permutations
Choosing a committee of $4$	No	combinations
Choosing a chair, a secretary and two ordinary members	Partly	split the roles
Dealing a hand of $5$ cards	No	combinations

A useful test: if swapping two of the chosen items gives a different outcome, order matters. Swapping two committee members gives the same committee; swapping the gold and silver medallists does not give the same result.

From permutations to combinations

Choose $3$ letters from A, B, C, D, E. If order mattered there would be ${}^{5}P_{3} = 60$ ordered choices. But every selection, say $\{A, B, C\}$ , appears $3! = 6$ times among those $60$ (ABC, ACB, BAC, BCA, CAB, CBA). So the number of selections is $\dfrac{60}{6} = 10$ .

Definition

A combination of $r$ objects from $n$ different objects is an unordered selection of $r$ of them. The number of such combinations is

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

Both notations ${}^{n}C_{r}$ and $\dbinom{n}{r}$ are used on Cambridge papers. Your calculator has an ${}^{n}C_{r}$ key; use it.

Key result

Useful facts:

{}^{n}C_{0} = {}^{n}C_{n} = 1, \qquad {}^{n}C_{1} = n, \qquad {}^{n}C_{r} = {}^{n}C_{n - r}.

The last fact says choosing $r$ items to take is the same as choosing the $n - r$ to leave behind. For example ${}^{10}C_{8} = {}^{10}C_{2} = 45$ .

Selections from more than one group

When a selection must contain a certain number from each of several groups, choose from each group separately and multiply (the multiplication principle). When there are several separate cases, count each case and add.

Method

Committee and team questions

Identify the groups (men and women, boys and girls, red and blue) and the total to be chosen.
List the cases that satisfy the condition, for example "at least $2$ women" in a committee of $4$ means $2$ , $3$ or $4$ women.
For each case, multiply the combinations from each group: ${}^{\text{women}}C_{w} \times {}^{\text{men}}C_{m}$ .
Add the cases.
If the cases are many, count the complement instead and subtract from the total.

"At least one"

"At least one woman" is the complement of "no women", so

\text{number with at least one woman} = \text{total} - \text{number with no women}.

This is almost always the fastest route.

Watch out

The "at least one" trap. For a committee of $4$ from $7$ men and $5$ women with at least one woman, it is tempting to write ${}^{5}C_{1} \times {}^{11}C_{3}$ : choose a woman, then any $3$ others. This overcounts. A committee with two women, $W_1$ and $W_2$ , is counted once when $W_1$ is "the woman" and again when $W_2$ is. The correct answer is ${}^{12}C_{4} - {}^{7}C_{4} = 495 - 35 = 460$ , whereas the faulty product gives $5 \times 165 = 825$ .

Particular people included or excluded

If a particular person must be chosen, put them in and choose the rest from the others.
If a particular person must not be chosen, remove them and choose from the others.
If two people refuse to serve together, count all selections and subtract those that contain both of them.

Selections followed by arrangements

Some questions first choose a group, then arrange it. Count the selections with combinations, then multiply by the number of arrangements of each selection.

\text{number of ways} = (\text{number of selections}) \times (\text{number of arrangements of each selection}).

For example, to choose $3$ of $8$ letters and arrange them in a line, ${}^{8}C_{3} \times 3! = 56 \times 6 = 336 = {}^{8}P_{3}$ , as it should be.

Dividing into groups

Splitting people into groups is a run of selections. To split $9$ people into groups of $4$ , $3$ and $2$ : choose the $4$ ( ${}^{9}C_{4}$ ), then the $3$ from the remaining $5$ ( ${}^{5}C_{3}$ ), and the last $2$ are forced. That is ${}^{9}C_{4} \times {}^{5}C_{3} = 126 \times 10 = 1260$ ways.

If some groups are the same size and unlabelled, divide by the number of ways of ordering those groups, because otherwise each division is counted once for each order. Nine people into three groups of $3$ : ${}^{9}C_{3} \times {}^{6}C_{3} = 1680$ ordered choices, but each division has been counted $3! = 6$ times, so there are $\dfrac{1680}{6} = 280$ divisions. If the groups are labelled (Team Red, Team Blue, Team Green), do not divide.

Selections with repeated items

Selecting letters from a word with repeated letters, such as $4$ letters from CHOCOLATE, needs cases, because two Cs are indistinguishable and a selection is identified only by which letters it contains. Split by how many of the repeated letters are used.

Combinations in probability

If $r$ items are chosen at random from $n$ , every one of the ${}^{n}C_{r}$ selections is equally likely. So

P(\text{event}) = \frac{\text{number of selections with the property}}{{}^{n}C_{r}}.

This is often the quickest way to handle drawing several items without replacement, and it avoids having to multiply by the number of orders on a tree diagram. See probability for the tree-diagram approach.

Worked examples

A committee with conditions (routine)

A committee of $4$ is chosen from $7$ men and $5$ women. Find the number of different committees

(a) in total, (b) with exactly $2$ women, (c) with at least one woman.

Solution

(a) ${}^{12}C_{4} = 495$ .

(b) Choose $2$ of the $5$ women and $2$ of the $7$ men: ${}^{5}C_{2} \times {}^{7}C_{2} = 10 \times 21 = 210$ .

Particular people

A team of $5$ is chosen from $10$ people, who include Asha and Ben. Find the number of teams

(a) that include Asha but not Ben,

(b) that do not include both Asha and Ben.

Solution

(a) Put Asha in and remove Ben. Choose the other $4$ from the remaining $8$ : ${}^{8}C_{4} = 70$ .

(b) Teams containing both: put both in, choose $3$ from the other $8$ : ${}^{8}C_{3} = 56$ . All teams: ${}^{10}C_{5} = 252$ . Teams not containing both: $252 - 56 = 196$ .

Note "not both" includes teams with Asha only, Ben only, and neither.

Select, then arrange

Three boys are chosen from $5$ and two girls from $4$ . The five chosen children then stand in a line with a girl at each end. How many different lines are possible?

Solution

Selections: ${}^{5}C_{3} \times {}^{4}C_{2} = 10 \times 6 = 60$ .

Arrangements of each selection: the two chosen girls go at the ends in $2!$ ways, and the three boys fill the middle in $3!$ ways: $2 \times 6 = 12$ .

Total $60 \times 12 = 720$ .

Probability with combinations

A bag contains $6$ red and $4$ blue discs. Three discs are taken at random without replacement. Find the probability that exactly $2$ are red.

Solution

All ${}^{10}C_{3} = 120$ selections are equally likely. Selections with $2$ red and $1$ blue: ${}^{6}C_{2} \times {}^{4}C_{1} = 15 \times 4 = 60$ .

P(\text{exactly 2 red}) = \frac{60}{120} = \frac{1}{2}.

By a tree diagram the same answer needs three orders: $3 \times \tfrac{6}{10} \times \tfrac{5}{9} \times \tfrac{4}{8} = \tfrac{1}{2}$ .

Dividing into groups (exam style)

Nine students are to be divided into groups.

(a) In how many ways can they be divided into a group of $4$ , a group of $3$ and a group of $2$ ?

(b) In how many ways can they be divided into three groups of $3$ ?

(c) In how many ways can they be divided into three groups of $3$ if two particular students, Kai and Lin, must be in the same group?

Solution

(a) ${}^{9}C_{4} \times {}^{5}C_{3} \times {}^{2}C_{2} = 126 \times 10 \times 1 = 1260$ .

(b) Choosing groups one after another gives ${}^{9}C_{3} \times {}^{6}C_{3} \times {}^{3}C_{3} = 84 \times 20 = 1680$ , but the three groups are not labelled, so each division has been counted $3! = 6$ times. Answer $\dfrac{1680}{6} = 280$ .

(c) Kai and Lin's group needs one more member: ${}^{7}C_{1} = 7$ ways. The remaining $6$ students form two unlabelled groups of $3$ : $\dfrac{{}^{6}C_{3}}{2!} = \dfrac{20}{2} = 10$ ways. Total $7 \times 10 = 70$ .

Selecting letters with repeats (exam-hard)

Find the number of different selections of $4$ letters from the $9$ letters of the word CHOCOLATE.

Solution

CHOCOLATE contains C twice, O twice, and H, L, A, T, E once each: $7$ different letters. A selection is determined by which letters it contains, so split by how many repeated pairs are used.

No letter used twice: choose $4$ of the $7$ different letters: ${}^{7}C_{4} = 35$ .
Exactly one pair (CC or OO): choose the pair in $2$ ways, then $2$ different letters from the other $6$ : $2 \times {}^{6}C_{2} = 2 \times 15 = 30$ .
Both pairs: CCOO, $1$ way.

Total $35 + 30 + 1 = 66$ .

Watch out

Using permutations for a selection. A committee of $4$ from $12$ is ${}^{12}C_{4} = 495$ , not ${}^{12}P_{4} = 11880$ . Only use ${}^{n}P_{r}$ when the chosen items are given different roles or positions.

Watch out

Adding when you should multiply. " $2$ women and $2$ men" is ${}^{5}C_{2} \times {}^{7}C_{2}$ . Adding is for separate cases joined by "or" (" $2$ women or $3$ women").

Watch out

Dividing by group orders when the groups are labelled or of different sizes. Only divide when groups are the same size and interchangeable. Groups of $4$ , $3$ and $2$ cannot be confused with each other, so there is nothing to divide by.

Exam tip

Write each case on its own line with its count, then add: for example " $4W$ : ${}^{5}C_{4} \times {}^{7}C_{0} = 5$ ". Examiners award marks per correct case.
For "at least" questions, decide quickly whether the complement has fewer cases; it usually does.
Before multiplying by $r!$ or similar, ask "does order matter here?" in words.
Probability answers can be left as exact fractions or given to 3 significant figures; counts must be exact integers.
"Not both" and "neither" mean different things; underline them in the question.

Summary

Order matters: permutations. Order does not matter: combinations.
${}^{n}C_{r} = \dfrac{n!}{r!\,(n - r)!} = \dfrac{{}^{n}P_{r}}{r!}$ , and ${}^{n}C_{r} = {}^{n}C_{n - r}$ .
From several groups: multiply within a case ("and"), add across cases ("or").
"At least one" $=$ total $-$ none. Never fix one and choose the rest freely.
Must include: put them in. Must exclude: take them out. Not together: total $-$ both.
Select, then arrange: multiply the number of selections by the arrangements of each.
Equal-sized unlabelled groups: divide by the number of orders of those groups.
Probability: favourable selections $\div$ ${}^{n}C_{r}$ .

Practice questions

Question

In how many ways can $3$ books be chosen from $8$ different books?
A team of $5$ is chosen from $6$ boys and $4$ girls. Find the number of teams with (a) exactly $3$ boys, (b) at least one girl.
A committee of $6$ is chosen from $8$ men and $6$ women. Find the number of committees with more women than men.
A committee of $4$ is chosen from $9$ people. Two of them refuse to serve together. How many committees are possible?
A box contains $20$ light bulbs, of which $5$ are faulty. Four bulbs are chosen at random. Find the probability that at least one is faulty.
Find $n$ given that ${}^{n}C_{2} = 45$ .
Two vowels and two consonants are chosen from the letters of EQUATION and then arranged in a line. How many different arrangements are possible?
Ten people are split into a group of $6$ and a group of $4$ . Find the number of ways this can be done (a) with no restriction, (b) if two particular people must be in the same group.
Find the number of different selections of $3$ letters from the letters of PROBABILITY.
A committee of $5$ is chosen from $6$ men and $5$ women, who include a married couple, Mr and Mrs Xu. The committee must contain at least $2$ women, and Mr and Mrs Xu cannot both be on it. Find the number of possible committees.

Answers

${}^{8}C_{3} = 56$ .
(a) ${}^{6}C_{3} \times {}^{4}C_{2} = 20 \times 6 = 120$ . (b) Total ${}^{10}C_{5} = 252$ ; all-boy teams ${}^{6}C_{5} = 6$ ; at least one girl $= 252 - 6 = 246$ .
More women than men means $4$ , $5$ or $6$ women. $4W\,2M$ : ${}^{6}C_{4} \times {}^{8}C_{2} = 15 \times 28 = 420$ . $5W\,1M$ : ${}^{6}C_{5} \times {}^{8}C_{1} = 6 \times 8 = 48$ . $6W$ : ${}^{6}C_{6} = 1$ . Total $469$ .
All committees ${}^{9}C_{4} = 126$ . With both of the pair: ${}^{7}C_{2} = 21$ . Answer $126 - 21 = 105$ .
$P(\text{no faulty}) = \dfrac{{}^{15}C_{4}}{{}^{20}C_{4}} = \dfrac{1365}{4845} = 0.2817\ldots$ , so $P(\text{at least one faulty}) = 1 - 0.2817 = 0.718$ (3 s.f.).
$\dfrac{n(n - 1)}{2} = 45 \Rightarrow n^2 - n - 90 = 0 \Rightarrow (n - 10)(n + 9) = 0$ , so $n = 10$ (since $n > 0$ ).
EQUATION has $5$ vowels (E, U, A, I, O) and $3$ consonants (Q, T, N), all different. Selections: ${}^{5}C_{2} \times {}^{3}C_{2} = 10 \times 3 = 30$ . Each selection of $4$ letters can be arranged in $4! = 24$ ways. Total $30 \times 24 = 720$ .
(a) Choose the group of $6$ ; the rest form the group of $4$ : ${}^{10}C_{6} = 210$ . (b) Both in the group of $6$ : choose $4$ more from $8$ : ${}^{8}C_{4} = 70$ . Both in the group of $4$ : choose $2$ more from $8$ : ${}^{8}C_{2} = 28$ . Total $70 + 28 = 98$ .
PROBABILITY: B twice, I twice, and P, R, O, A, L, T, Y once each, so $9$ different letters. No repeated letter: ${}^{9}C_{3} = 84$ . One pair (BB or II) plus one of the other $8$ letters: $2 \times 8 = 16$ . Total $84 + 16 = 100$ .
First ignore the couple. Committees with at least $2$ women: total ${}^{11}C_{5} = 462$ , minus $0$ women ( ${}^{6}C_{5} = 6$ ), minus exactly $1$ woman ( ${}^{5}C_{1} \times {}^{6}C_{4} = 75$ ): $462 - 6 - 75 = 381$ .

Now subtract those containing both Mr and Mrs Xu. With both in, $3$ more are chosen from the other $5$ men and $4$ women, and at least $1$ of these must be a woman (Mrs Xu is already one): ${}^{9}C_{3} - {}^{5}C_{3} = 84 - 10 = 74$ .

Answer $381 - 74 = 307$ .

Permutation or combination?

From permutations to combinations

Selections from more than one group

"At least one"

Particular people included or excluded

Selections followed by arrangements

Dividing into groups

Selections with repeated items

Combinations in probability

Worked examples

Practice questions

Console