Permutations and Combinations Revision Notes — 9709 Paper 5

topic	marks/paper
Discrete Random Variables	13.2
The Normal Distribution	11.6
Probability	11.2
Permutations and Combinations	9.8
Representation of Data	9.3

sub-topic	parts	marks	sections
Arrangements in a line with restrictions	63	194	02, 10–14
Permutations and combinations for selection problems	50	163	01, 03–08
Arrangements in a line with repetition	47	124	09–13

Counting without listing: multiply, add, subtract

Syllabus requirement · §5.2

“

understand the terms permutation and combination, and solve simple problems involving selections

”

Suppose a café sells $3$ sandwiches and $4$ drinks, and a meal is one sandwich with one drink. You could write every meal down — but with bigger numbers (the letters of a ten-letter word, the committees in a club of twenty) listing is hopeless. This whole topic is about getting the number of possibilities without listing them.

Three rules do all the work. Everything later in the note — permutations, combinations, blocks, gaps — is one of these three rules applied carefully.

Rule 1 — the multiplication principle ("and")

If a job is done in stages, and

stage 1 can be done in $a$ ways,
then, whichever way stage 1 was done, stage 2 can be done in $b$ ways,

then the whole job can be done in $a \times b$ ways. With more stages, keep multiplying.

Why multiply? Each of the $a$ first choices can be followed by each of the $b$ second choices. That is $b$ outcomes for the first choice, $b$ more for the second, and so on — $a$ lots of $b$ , which is $a \times b$ . To keep the picture small, the tree below uses a smaller café with only $2$ sandwiches and $3$ drinks: $2$ branches, each splitting into $3$ , gives $2 \times 3 = 6$ ends. The café above, with $3$ sandwiches and $4$ drinks, works the same way: $3 \times 4 = 12$ meals.

Two sandwiches, each followed by three drinks: every path from left to right is one meal, and there are 2 × 3 = 6 paths.

A quick way to organise a multiplication-principle count is to draw one slot for each stage and write the number of choices in it. The word "and" in the description ("a sandwich and a drink") is the usual signal to multiply.

The key phrase is whichever way stage 1 was done. Earlier choices can change which options are left (a book already put on the shelf cannot be put there again), but the number of choices at each stage must not depend on which choice was made earlier. When it does, split the count into cases instead (Rule 2).

The multiplication principle with slots

A café offers $3$ sandwiches, $4$ drinks and $2$ desserts. A lunch deal is one sandwich, one drink and one dessert. How many different lunch deals are there?

Show full working

One slot per stage, with the number of choices for that stage written in it. Multiply along the slots.

1
Identify the stages. A lunch deal is made in three stages: choose a sandwich, then a drink, then a dessert.
Before counting anything, decide what one 'outcome' is and how it is built up. Here one outcome is a (sandwich, drink, dessert) triple.
2
Count the choices at each stage. Sandwich: $3$ . Drink: $4$ , whichever sandwich was chosen. Dessert: $2$ , whichever sandwich and drink were chosen.
The phrase 'whichever … was chosen' is the check that multiplying is allowed: the number of drinks available never depends on the sandwich.
3
Multiply the stage counts. $3 \times 4 \times 2 = 24$
Rule 1: each of the 3 sandwiches pairs with each of the 4 drinks (12 pairs), and each pair goes with either dessert (24).

Answer

$24$ lunch deals.

Rule 2 — the addition principle ("or")

If the outcomes you want fall into separate cases that cannot happen together, count each case on its own and add.

Example: you can travel to town by one of $3$ buses or by one of $2$ trains. A journey is a bus or a train, never both, so there are $3 + 2 = 5$ ways to travel.

The cases must not overlap (a journey cannot be both a bus and a train), and between them they must cover every outcome you want. Most of the long questions in this topic are "list the cases, count each with Rule 1, add them with Rule 2".

Rule 3 — the complement ("everything minus what you don't want")

Sometimes the outcomes you don't want are easier to count than the ones you do. Then

\text{wanted} = \text{total} - \text{unwanted}.

(You will meet this same idea again for probabilities in §5.3.) It is strongest for the words "at least one" (the unwanted case is "none") and "not together" (the unwanted case is "together", which is easy to count — see §11).

Rules 2 and 3 on the same count

A three-digit lock code uses the digits $0$ to $9$ , and digits may be repeated (so $007$ and $555$ are allowed). How many codes contain at least one $7$ ?

Show full working

1
Count all the codes (Rule 1). Each of the three positions can be any of the $10$ digits, whatever the other positions are: $10 \times 10 \times 10 = 1000$
Repetition is allowed, so choosing a digit for one slot does not use it up — every slot has all 10 choices.
2
Name the unwanted outcomes. "At least one $7$ " fails only when the code has no $7$ at all.
The opposite of 'at least one' is always 'none'. That is one simple case, whereas 'at least one 7' would need three cases (one 7, two 7s, three 7s).
3
Count the codes with no $7$ (Rule 1 again). Each position can be any digit except $7$ , so $9$ choices each: $9 \times 9 \times 9 = 729$
Removing the 7 leaves 9 digits for every position, whatever the other positions hold.
4
Subtract (Rule 3). $1000 - 729 = 271$
Every code either contains a 7 or it doesn't, so wanted + unwanted = total.
5
Check by cases (Rule 2) — exactly one $7$ . Choose which position holds the $7$ : $3$ ways. The other two positions are any non-7 digit: $9 \times 9 = 81$ . So $3 \times 81 = 243$
Now we count the wanted codes directly, split into cases by how many 7s there are. The cases cannot overlap, so Rule 2 lets us add them.
6
Check — exactly two $7$ s. Choose the position of the one non-7 digit: $3$ ways; it can be any of $9$ digits. So $3 \times 9 = 27$
7
Check — three $7$ s. Only $777$ : $1$ code.
8
Check — add the cases. $243 + 27 + 1 = 271$ ✓
Both routes agree, and the complement took one line instead of three cases — that is exactly why it is worth spotting.

Answer

$271$ codes.

'At least one' is the classic signal for the complement: total minus 'none'.

Slots with a restriction: fill the fussy slot first

When one slot has a special condition (the first digit of a number cannot be $0$ ; the last digit must be odd), fill that slot first, then fill the others from whatever is left. If you fill the free slots first, the number of choices left for the fussy slot depends on which digits were used — and Rule 1 stops working.

Filling the fussy slot first

Three-digit numbers are made from the digits $0, 1, 2, 3, 4$ , and no digit may be used more than once. How many such numbers are there?

Show full working

1
Spot the fussy slot. The hundreds digit cannot be $0$ (otherwise the number would only have two digits). The tens and units have no special condition.
The slot with a condition is the one to fill first.
2
Fill the hundreds digit first. It can be $1, 2, 3$ or $4$ : $4 \text{ choices}$
3
Fill the tens digit. Any of the five digits except the one already used — and $0$ is now allowed: $5 - 1 = 4 \text{ choices}$
Whichever digit went in the hundreds, exactly one digit is used up, so there are always 4 left. The number of choices does not depend on which digit was used.
4
Fill the units digit. Any digit except the two already used: $5 - 2 = 3 \text{ choices}$
5
Multiply the slots. $4 \times 4 \times 3 = 48$
Rule 1: every stage has a fixed number of choices, whatever came before.
6
See what goes wrong the other way round. Suppose you fill the units first and the tens next. If $0$ has been used there, the hundreds has $3$ choices left; if $0$ has not been used, it has only $2$ (not $0$ , and not the two used digits). There is no single number to put in the hundreds slot.
This is why the fussy slot goes first: it keeps every later slot's count fixed.

Answer

$48$ numbers.

Three-digit numbers with different digits

9709/61 M/J 2016 Q6(a)(i)3 marks

Find how many numbers there are between $100$ and $999$ in which all three digits are different.

Show full working

Fill the hundreds slot first (it cannot be 0), then the tens (any digit except the one used), then the units.

1
Say what an outcome is. A number between $100$ and $999$ is a three-digit number: hundreds, tens, units. The hundreds digit cannot be $0$ , and the three digits must all be different.
Writing the rules down before counting stops you forgetting the 'no leading zero' condition, which is what makes this slot fussy.
2
Fill the fussy slot first — the hundreds digit. It can be $1$ to $9$ : $9 \text{ choices}$
If the tens digit were chosen first, the number of choices left for the hundreds would depend on whether the tens digit was 0 or not — that breaks the multiplication principle.
3
Fill the tens digit. Any of the ten digits $0$ – $9$ except the one already used: $10 - 1 = 9 \text{ choices}$
0 is allowed here, which is why there are 9 choices again, not 8.
4
Fill the units digit. Any digit except the two already used: $10 - 2 = 8 \text{ choices}$
5
Multiply the slots. $9 \times 9 \times 8 = 648$
This is the mark scheme's 9 × 9 × 8 = 648.

Answer

$648$ numbers.

Fill the slot with the restriction first; then every later slot has a fixed number of choices, whatever came before.

Common mistakes

Adding the stage counts: " $3$ sandwiches and $4$ drinks give $3 + 4 = 7$ meals"
Stages done one after another multiply: $3 \times 4 = 12$ meals
Add only for separate cases (a bus OR a train). A meal needs a sandwich AND a drink.
Filling the free slots first and the restricted slot last
Fill the restricted slot first, then the rest
The number of choices left for a restricted slot depends on which digits were used earlier, so it has no single value.
Counting "at least one" by listing every case and missing one
Use total minus "none"
The complement has only one case to count, so there is nothing to miss.

Your turn

Draw the slots, fill the fussy one first, and decide whether each word means multiply, add or subtract.

1
A car registration is two letters from $\{A, B, C, D, E\}$ followed by two digits from $\{1, 2, \ldots, 9\}$ . Letters may be repeated and digits may be repeated. How many registrations are possible?
Stuck? Show hint
Four slots; repetition allowed means every slot keeps all of its choices.
Show solution
1. 1
  Slots: letter, letter, digit, digit.
2. 2
  Choices per slot: $5$ , $5$ , $9$ , $9$ (repetition allowed, so nothing is used up).
  Using a letter does not remove it, so the second letter slot still has all 5 letters; the same for the digits.
3. 3
  Multiply the letter slots and the digit slots: $5 \times 5 = 25$ and $9 \times 9 = 81$ .
4. 4
  Multiply the two results: $25 \times 81 = 2025$ .
  Rule 1: the letters and the digits are chosen one stage after another.
Answer
$2025$ registrations.
2
A student chooses either one of $6$ science options or one of $4$ language options, and then, whatever they chose, one of $3$ sports. How many different choices are there?
Stuck? Show hint
"Either … or" is Rule 2; "and then" is Rule 1.
Show solution
1. 1
  First choice (Rule 2): a science option or a language option, which cannot both happen: $6 + 4 = 10$ ways.
  The student takes one or the other, never both, so the two cases are added.
2. 2
  Second choice: $3$ sports, whatever the first choice was.
3. 3
  Multiply the two stages (Rule 1): $10 \times 3 = 30$ .
Answer
$30$ choices.
3
Four-digit PIN codes use the digits $0$ – $9$ , with repetition allowed. How many PINs contain at least one $0$ ?
Stuck? Show hint
Total minus the PINs with no 0 at all.
Show solution
1. 1
  Total: $10^4 = 10\,000$ .
2. 2
  No $0$ at all: $9$ choices per position, $9^4 = 6561$ .
  The opposite of 'at least one 0' is 'no 0', which is one easy case.
3. 3
  Complement: $10\,000 - 6561 = 3439$ .
  Rule 3: wanted = total − unwanted.
Answer
$3439$ PINs.
4
How many odd three-digit numbers have all three digits different?
Stuck? Show hint
Two slots are fussy: the units (must be odd) and the hundreds (not 0, and not the units digit). Fill the units first, then the hundreds.
Show solution
1. 1
  Units first: it must be odd — $1, 3, 5, 7$ or $9$ : $5$ choices.
2. 2
  Hundreds next: not $0$ and not the units digit. From the nine digits $1$ – $9$ , remove the one odd digit already used: $8$ choices.
  The units digit is odd, so it is always one of 1–9 — that is why exactly one choice is removed from the nine, whichever odd digit was used.
3. 3
  Tens last: any digit except the two used, including $0$ : $10 - 2 = 8$ choices.
  The tens slot has no condition of its own, so only the two used digits are ruled out.
4. 4
  Multiply: $5 \times 8 \times 8 = 320$ .
Answer
$320$ numbers.

Checking your access…

Can you do all of these?

Multiply for stages done one after another; add for separate cases; subtract the unwanted from the total
Fill a restricted slot or position first, then everything else
Swap two chosen objects: if the outcome changes it is a permutation, if not a combination
Put compulsory people in first and take excluded people out of the pool — shrink both the places and the pool
For 'at least', 'at most', 'more than' conditions, write the full table of splits before any arithmetic, and check the two ends of the list
'Not both' = total − both; 'at least one of' = total − neither; 'exactly one of' = (only A) + (only B), which is 2 × (only A) when A and B are interchangeable
Selecting letters from a word: tally the word, case on the repeated letters, fill the rest from the letters that appear once
Dividing into groups: divide by k! only for k groups of the same size with no labels (towns, cars, tables and rows are labels)
Arrangements with repeats: one factorial in the denominator for each repeated letter — and update the tally after fixing a letter
Block method: arrange the units, then multiply by the orders inside each block (1 for identical letters or a fixed order)
Two objects apart: total − together. No two of several apart: gap method (k objects make k + 1 gaps)
'Not all together' is total − all together; it is not the same as 'no two together'
With fixed ends, every later count is of the middle letters only
One group together and another apart: (first together) − (both together)
Exactly k between: n − k − 1 position pairs, × 2 only if the two objects are different, then arrange the rest
With a block and a 'k between' condition, first ask whether the block can fit between the pair (count letters, not units)
'At least k between any two' of three or more objects: list the possible sets of positions
Together but not at an end: (together) − (together with the block at an end)
Ends chosen from a pool (an adult at each end): an ordered pair, ⁿP₂
In rows or at tables, seat the restricted people first; adjacent means next to each other in the same row
Letters selected at random for a probability: count tiles (²C₁ for one of two Es), top and bottom