Combinations – OCR FSMQ Additional Maths

1 What a Combination Is

EN5: enumerate an unordered subset — a combination — of $r$ elements from a set of $n$ distinct objects, using the notation ${}^nC_r$.

In a combination you care only which objects were chosen, never the order they were chosen in. $\{A, B, C\}$ and $\{C, A, B\}$ are the same combination.

The combination formula

${}^nC_r = \binom{n}{r} = \dfrac{n!}{r!\,(n-r)!} = \dfrac{{}^nP_r}{r!}$

Where the $r!$ comes from. Start with the ${}^nP_r$ ordered selections. Every unordered set of $r$ objects has been counted $r!$ times, once for each of its orderings — so divide by $r!$ to count each set exactly once.

Worked Example 1 — The specification's example

How many ways are there of choosing two people out of a group of ten to sit on a committee?

①Both committee members have the same role, so order does not matter.

②${}^{10}C_2 = \dfrac{10 \times 9}{2 \times 1} = 45$

③Compare with the two different prizes version: ${}^{10}P_2 = 90$, exactly twice as many.

The factor of $2$ is $2!$ — each pair $\{A,B\}$ gave two orderings, $AB$ and $BA$. Seeing where that factor comes from is the heart of this topic.

2 Calculating ${}^nC_r$ Efficiently

Write $r$ descending factors starting at $n$ on the top.
Write $r!$ on the bottom.
Cancel before multiplying — the answer is always a whole number.
If $r$ is more than half of $n$, use the symmetry first.

Useful values and identities

$\binom{n}{0} = 1$ · $\binom{n}{1} = n$ · $\binom{n}{2} = \dfrac{n(n-1)}{2}$ · $\binom{n}{n} = 1$
$\binom{n}{r} = \binom{n}{n-r}$

Worked Example 2 — Cancel as you go

Evaluate ${}^{12}C_4$.

①${}^{12}C_4 = \dfrac{12 \times 11 \times 10 \times 9}{4 \times 3 \times 2 \times 1}$

②Cancel: $\dfrac{12}{4 \times 3} = 1$, and $\dfrac{10}{2} = 5$.

③Left with $11 \times 5 \times 9 = 495$

The answer must be a whole number. If yours is not, you have made an arithmetic error — ${}^nC_r$ counts things, so it cannot be a fraction.

Worked Example 3 — Using the symmetry

Evaluate ${}^{50}C_{48}$.

①$48$ factors would be absurd. Use $\binom{n}{r} = \binom{n}{n-r}$:

②${}^{50}C_{48} = {}^{50}C_2 = \dfrac{50 \times 49}{2} = 1225$

③Why it works: choosing $48$ to include is the same as choosing the $2$ to leave out.

3 Choosing From Several Groups

The pattern

Choose from each group separately, then multiply — the product rule again

Worked Example 4 — A mixed committee

A committee of $5$ is chosen from $7$ women and $6$ men. How many committees contain exactly $3$ women?

①$3$ women from $7$: ${}^7C_3 = \dfrac{7 \times 6 \times 5}{6} = 35$

②Then $2$ men from $6$: ${}^6C_2 = \dfrac{6 \times 5}{2} = 15$

③These choices are independent, so multiply: $35 \times 15 = 525$

Multiply, do not add. Every choice of women can pair with every choice of men, which is multiplication. Adding would answer a completely different question.

Worked Example 5 — "At least" by cases

From the same $7$ women and $6$ men, how many committees of $5$ contain at least $4$ women?

①"At least $4$" means exactly $4$ or exactly $5$ — two separate cases, so we will add.

②Exactly $4$ women: ${}^7C_4 \times {}^6C_1 = 35 \times 6 = 210$

③Exactly $5$ women: ${}^7C_5 \times {}^6C_0 = 21 \times 1 = 21$

④$210 + 21 = 231$

Multiply within a case, add between cases. Note ${}^7C_4 = {}^7C_3 = 35$ by symmetry, and ${}^6C_0 = 1$ — there is exactly one way to choose no men.

Worked Example 6 — "At least one" by complement

A team of $4$ is chosen from $10$ players, of whom $3$ are goalkeepers. How many teams include at least one goalkeeper?

①Total teams: ${}^{10}C_4 = \dfrac{10 \times 9 \times 8 \times 7}{24} = 210$

②Teams with no goalkeeper use only the $7$ others: ${}^7C_4 = 35$

③$210 - 35 = 175$

④By cases, as a check: one keeper $3 \times {}^7C_3 = 3 \times 35 = 105$; two keepers $3 \times {}^7C_2 = 3 \times 21 = 63$; three keepers $1 \times {}^7C_1 = 7$.

⑤$105 + 63 + 7 = 175$ ✓

Use the complement when you can. One subtraction beat three cases here, and there was less to get wrong.

4 Combinations in Probability

When every selection is equally likely

$P(\text{event}) = \dfrac{\text{number of selections giving the event}}{\text{total number of selections}}$

Worked Example 7 — A probability by counting

Three counters are drawn at random from a bag containing $5$ red and $4$ blue. Find the probability that all three are red.

①Total ways to draw $3$ from $9$: ${}^9C_3 = \dfrac{9 \times 8 \times 7}{6} = 84$

②Ways to draw $3$ reds from $5$: ${}^5C_3 = 10$

③$P(\text{all red}) = \dfrac{10}{84} = \dfrac{5}{42}$

④Check with a tree-diagram calculation: $\dfrac{5}{9} \times \dfrac{4}{8} \times \dfrac{3}{7} = \dfrac{60}{504} = \dfrac{5}{42}$ ✓

Both methods always agree. Counting with combinations is usually quicker when the question asks about a mixture, such as "exactly two red".

5 Quick Reference

Meaning

An unordered selection of $r$ from $n$.

Formula

${}^nC_r = \dfrac{n!}{r!(n-r)!}$.

Link to $P$

${}^nC_r = {}^nP_r \div r!$.

Symmetry

$\binom{n}{r} = \binom{n}{n-r}$.

Edge cases

$\binom{n}{0} = \binom{n}{n} = 1$.

Whole number

Always — a fraction means an error.

Several groups

Choose from each, then multiply.

Within / between

Multiply within a case, add between cases.

"At least one"

Total minus none.

Probability

Favourable selections over total selections.

6 Practice Questions

Question 1

Evaluate ${}^7C_2$ and ${}^9C_4$.

▶ Show solution

${}^7C_2 = \dfrac{7 \times 6}{2} = 21$

${}^9C_4 = \dfrac{9 \times 8 \times 7 \times 6}{24} = 126$

Question 2

How many ways are there of choosing $3$ pizza toppings from a list of $8$?

▶ Show solution

Order irrelevant: ${}^8C_3 = \dfrac{8 \times 7 \times 6}{6} = 56$

Question 3

Evaluate ${}^{30}C_{28}$.

▶ Show solution

Use the symmetry: ${}^{30}C_{28} = {}^{30}C_2$.

$= \dfrac{30 \times 29}{2} = 435$

Question 4

A team of $5$ is chosen from $6$ boys and $5$ girls. How many teams have exactly $2$ boys?

▶ Show solution

$2$ boys from $6$: ${}^6C_2 = 15$

$3$ girls from $5$: ${}^5C_3 = 10$

$15 \times 10 = 150$

Question 5

From a pack of $52$ cards, how many different hands of $5$ cards are possible?

▶ Show solution

${}^{52}C_5 = \dfrac{52 \times 51 \times 50 \times 49 \times 48}{120}$

$= 2\,598\,960$

Question 6

Solve ${}^nC_2 = 36$.

▶ Show solution

$\dfrac{n(n-1)}{2} = 36$, so $n(n-1) = 72$.

$n^2 - n - 72 = 0$, giving $(n-9)(n+8) = 0$.

$n = 9$ (rejecting $n = -8$).

Question 7

A group of $4$ is chosen from $9$ people, two of whom are twins. How many groups contain at least one twin?

▶ Show solution

Total: ${}^9C_4 = 126$

Groups with no twin, from the other $7$: ${}^7C_4 = 35$

$126 - 35 = 91$

Question 8

Two counters are taken at random from a bag of $6$ green and $4$ yellow. Find the probability that both are green.

▶ Show solution

Total ways: ${}^{10}C_2 = 45$

Both green: ${}^6C_2 = 15$

$P = \dfrac{15}{45} = \dfrac{1}{3}$

Question 9

Explain, without computing either side, why $\binom{n}{0} + \binom{n}{1} + \cdots + \binom{n}{n} = 2^n$.

▶ Show solution

The left side counts all the subsets of a set of $n$ objects, grouped by size: those with $0$ elements, then $1$, and so on up to $n$.

The right side counts the same subsets a different way: for each of the $n$ objects, decide independently whether to include it. That is $2$ choices, $n$ times, so $2^n$ subsets.

Both sides count every subset exactly once, so they are equal.

(Equivalently, substitute $x = 1$ into the expansion of $(1+x)^n$.)

Question 10

A box holds $12$ light bulbs, of which $3$ are faulty. Four bulbs are chosen at random.

(a) How many selections are possible? (b) Find the probability that none is faulty. (c) Find the probability that exactly one is faulty. (d) Find the probability that at least two are faulty, and check your three probabilities are consistent.

▶ Show solution

(a) ${}^{12}C_4 = \dfrac{12 \times 11 \times 10 \times 9}{24} = 495$

(b) All four from the $9$ good bulbs: ${}^9C_4 = 126$

$P(\text{none faulty}) = \dfrac{126}{495} = \dfrac{14}{55} = 0.2545\ldots$

(c) One faulty from $3$ and three good from $9$:

${}^3C_1 \times {}^9C_3 = 3 \times 84 = 252$

$P(\text{exactly one}) = \dfrac{252}{495} = \dfrac{28}{55} = 0.5090\ldots$

(d) "At least two" is the complement of "none or exactly one":

$P = 1 - \dfrac{14}{55} - \dfrac{28}{55} = 1 - \dfrac{42}{55} = \dfrac{13}{55} = 0.2363\ldots$

Consistency check by direct counting:

Exactly two faulty: ${}^3C_2 \times {}^9C_2 = 3 \times 36 = 108$

Exactly three faulty: ${}^3C_3 \times {}^9C_1 = 1 \times 9 = 9$

$108 + 9 = 117$, and $\dfrac{117}{495} = \dfrac{13}{55}$ ✓

Also $126 + 252 + 108 + 9 = 495$, accounting for every possible selection — a complete check on all four cases.

Combinations (EN5) · OCR FSMQ Additional Maths · Created with MathJax