5.1 Counting Principles and Permutations
AHL 1.10
- the addition principle (“or”) and the multiplication principle (“and then”)
- what a permutation is: an arrangement where order matters
- the number of ways to arrange \(n\) different objects, \(n!\)
- the number of ways to arrange \(r\) objects chosen from \(n\), \({}^n\mathrm{P}_r\)
- how to count arrangements with repetition allowed
Counting the number of ways something can happen is called combinatorics. You will use it again in probability (Unit 16).
The addition principle
Two events are mutually exclusive if they cannot both happen at the same time. For example, on one throw of a dice you cannot get a 1 and an even number.
Addition principle (“or”) Not in the formula booklet
If \(A\) can be done in \(n_1\) ways and \(B\) can be done in \(n_2\) ways, and \(A\) and \(B\) are mutually exclusive, then \(A\) or \(B\) can be done in \(n_1 + n_2\) ways.
Example 1 To travel from Singapore to Kuala Lumpur, Ravi can take one of 5 bus companies or one of 3 train services. In how many ways can he travel?
He takes a bus or a train (not both): \(5 + 3 = 8\) ways.
The multiplication principle
Multiplication principle (“and then”) Not in the formula booklet
If \(A\) can be done in \(n_1\) ways, and after that \(B\) can be done in \(n_2\) ways, then \(A\) followed by \(B\) can be done in \(n_1 \times n_2\) ways.
A tree diagram shows why: each of the \(n_1\) branches splits into \(n_2\) branches.
Example 2 There are 3 roads from town \(A\) to town \(B\), and 4 roads from \(B\) to \(C\). In how many ways can you drive from \(A\) to \(C\) through \(B\)?
Choose a road \(A \to B\) and then a road \(B \to C\): \(3 \times 4 = 12\) ways.
Example 3 Mei has 6 cousins. In how many ways can she invite some of them (at least one) to her party?
For each cousin there are 2 choices: invite or not invite. By the multiplication principle there are \(2^6 = 64\) ways to make all six choices. One of these invites nobody, which is not allowed:
\[ 2^6 - 1 = 63 \text{ ways}. \]
Permutations
A permutation is an ordered arrangement of objects. If changing the order gives a different result, we are counting permutations.
Example 4 Which of the following involve permutations (order matters)?
(a) Arranging 4 different photos in a row on a wall.
(b) Choosing 3 books from a list of 10 to take on holiday.
(c) Giving gold, silver and bronze medals to 3 of 8 runners.
(d) Making 4-digit PIN codes.
(e) Choosing 2 students from a class to go to a meeting.
(a), (c) and (d) are permutations: changing the order changes the result. In (b) and (e) only the group matters, not the order — these are combinations (see 5.3).
Arranging \(n\) different objects
Arrange the letters \(A\), \(B\), \(C\), \(D\) in a row. The first place can be filled in 4 ways, the second in 3 ways (one letter is used), the third in 2 ways, the last in 1 way:
\[ 4 \times 3 \times 2 \times 1 = 4! = 24 . \]
The symbol \(4!\) is read “4 factorial”. In general, for a positive integer \(n\),
\[ n! = n \times (n - 1) \times (n - 2) \times \cdots \times 2 \times 1 , \]
read “\(n\) factorial”: multiply all the whole numbers from \(n\) down to \(1\). We also define \(0! = 1\). (Factorials were introduced in 4.1.)
Arrangements of \(n\) different objects Not in the formula booklet
The number of ways to arrange \(n\) different objects in a row is \(n!\).
Example 5 A witness saw a car number plate. She remembers that it started with \(P\) or \(Q\), that the digits were \(2\), \(5\) and \(9\) in some order, and that the last three letters were \(X\), \(Y\) and \(Z\) in some order. How many number plates must the police check?
First letter: 2 ways. Digits: \(3! = 6\) ways. Last letters: \(3! = 6\) ways.
\[ 2 \times 6 \times 6 = 72 \text{ number plates}. \]
Arranging \(r\) objects out of \(n\)
If only \(r\) of the \(n\) places are filled, we stop after \(r\) factors:
\[ n \times (n - 1) \times \cdots \times (n - r + 1) = \frac{n!}{(n - r)!} . \]
This number is written \({}^n\mathrm{P}_r\) and read “\(n\) P \(r\)” — the number of permutations of \(r\) objects chosen from \(n\) (P stands for permutation). Some books write \(P(n, r)\) or \({}_n\mathrm{P}_r\). For example, \({}^9\mathrm{P}_4\) is “9 P 4”: start at \(9\) and multiply \(4\) numbers counting down, \(9 \times 8 \times 7 \times 6 = 3024\).
When all \(n\) objects are arranged (\(r = n\)): \({}^n\mathrm{P}_n = \dfrac{n!}{0!} = n!\), which agrees with the result above.
Permutations of \(r\) objects from \(n\) different objects In the HL formula booklet
\[ {}^n\mathrm{P}_r = \frac{n!}{(n - r)!}, \qquad r \le n \]
- \({}^n\mathrm{P}_r\): the number of permutations (ordered arrangements) of \(r\) objects chosen from \(n\)
- \(n\): the number of different objects to choose from
- \(r\): the number of objects arranged (\(r \le n\))
Example 6 Nine runners are in a race. In how many ways can the first four places be filled (no ties)?
\[ {}^9\mathrm{P}_4 = 9 \times 8 \times 7 \times 6 = 3024 \]
Repetition allowed
If each object can be used again, every place has all \(n\) choices.
Arrangements with repetition Not in the formula booklet
The number of arrangements of \(r\) objects from \(n\) different objects with repetition is \(n^r\).
Example 7 How many 3-digit numbers can be made from the digits \(1, 2, 3, 4, 5, 6, 7\) if
(a) no digit may be repeated, \(\qquad\) (b) digits may be repeated?
(a) \({}^7\mathrm{P}_3 = 7 \times 6 \times 5 = 210\). \(\qquad\) (b) \(7^3 = 343\).
Menu → Probability → Permutations, then type nPr(9,4) → 3024. For factorials: Menu → Probability → Factorial (!).
Common errors
| ✗ Wrong | ✓ Right | Why |
|---|---|---|
| Adding when both things happen | Multiply for “and then” | Add only for “either … or” (mutually exclusive). |
| \(2^6\) for “at least one” | \(2^6 - 1\) | Remove the case where nothing is chosen. |
| \({}^9\mathrm{P}_4 = \frac{9!}{4!}\) | \(\frac{9!}{5!}\) | Divide by \((n - r)!\). |
| \({}^7\mathrm{P}_3\) when repetition is allowed | \(7^3\) | With repetition, the number of choices does not go down. |
Exercises
1 A café offers 4 sandwiches and 3 salads. In how many ways can you choose one item? In how many ways can you choose one sandwich and one salad?
One item: \(4 + 3 = 7\). One of each: \(4 \times 3 = 12\).
2 A password has 2 letters (A–Z) followed by 3 digits (0–9). Repetition is allowed. How many passwords are possible?
\(26^2 \times 10^3 = 676\,000\).
3 In how many ways can 6 different books be arranged on a shelf?
\(6! = 720\).
4 A club has 12 members. In how many ways can it choose a president, a secretary and a treasurer (three different people)?
Order matters (different jobs): \({}^{12}\mathrm{P}_3 = 12 \times 11 \times 10 = 1320\).
5 How many 4-digit numbers can be made from the digits \(1, 3, 5, 7, 9\)
(a) without repetition,
(b) with repetition?
(a) \({}^5\mathrm{P}_4 = 120\). \(\qquad\) (b) \(5^4 = 625\).
6 A pizza can have any selection of 8 toppings (including no toppings). How many different pizzas are possible?
Each topping: in or out. \(2^8 = 256\).
7 Solve \({}^n\mathrm{P}_2 = 56\).
\(n(n - 1) = 56 \Rightarrow n^2 - n - 56 = 0 \Rightarrow (n - 8)(n + 7) = 0\), so \(n = 8\).
8 How many odd 3-digit numbers can be made from the digits \(2, 3, 4, 5, 6\) without repetition?
Fill the restricted place first. Last digit odd: 2 ways (3 or 5). Then the first two places: \(4 \times 3 = 12\). Total \(2 \times 12 = 24\).
9 A test has 10 true/false questions. In how many ways can a student answer all of them?
\(2^{10} = 1024\).
10 How many numbers between 100 and 999 (inclusive) have three different digits?
First digit 1–9: 9 ways. Second digit: any of 10 except the first: 9 ways. Third: 8 ways. \(9 \times 9 \times 8 = 648\).