When order matters
Eight runners race for a gold, a silver and a bronze medal. Ann winning gold, Ben silver and Cal bronze is a different result from Cal gold, Ben silver and Ann bronze, although the same three people have medals. The order they finish in matters.
An arrangement in which order matters is called a permutation. Counting the possible results of the race means counting permutations of 3 runners chosen from 8.
Counting down
Fill the medals one at a time. Any of the 8 runners can take gold. Whoever wins gold cannot also take silver, so 7 runners are left for silver, and then 6 for bronze.
Each choice is made after the one before, so the choices multiply: 8 × 7 × 6 = 336 possible results.
One box for each medal. Every medal given out leaves one runner fewer for the next: 8, then 7, then 6.
A small case drawn in full
With 4 runners and only gold and silver, there are 4 × 3 = 12 results. A grid shows all of them: one row for the gold winner, one column for the silver winner. The squares on the diagonal stay empty, because one runner cannot win both.
AB and BA are both in the grid, in different squares: A gold and B silver is not the same result as B gold and A silver.
Gold winner down the side, silver winner across the top. The 12 shaded squares are the results; the diagonal is empty because nobody wins two medals.
The notation nPr
The number of ways to arrange r things chosen from n different things is written nPr. It is the product of r factors, counting down from n: nPr = n × (n − 1) × … × (n − r + 1). For the medals, 8P3 = 8 × 7 × 6 = 336.
It is also written with factorials: nPr = n! ÷ (n − r)!. To see why, arrange all 8 runners: 8! orders. The first three places carry the medals and the last five carry nothing, and those five can be in any of 5! orders without changing the medal result. Dividing 8! by 5! removes them: 8! ÷ 5! = 40320 ÷ 120 = 336.
All 8 runners in a row. The shaded boxes are the five places without a medal, 5 × 4 × 3 × 2 × 1 = 5!, and dividing by 5! cancels them.
Two checks
Choose all n: nPn = n! ÷ 0! = n! ÷ 1 = n!, the number of ways to arrange the whole set in a row. This is one place where 0! = 1 is needed.
Choose one: nP1 = n! ÷ (n − 1)! = n. There are n ways to pick one thing, as there should be.
More permutations
A club of 12 members elects a president, a secretary and a treasurer, and no one holds two posts. The posts are different, so order matters: 12P3 = 12 × 11 × 10 = 1320 ways.
A four-digit code uses four different digits from 0 to 9. The order of the digits matters, since 1234 and 4321 are different codes: 10P4 = 10 × 9 × 8 × 7 = 5040 codes.
If the same thing may be used again, nothing is used up, and every place keeps all n choices: a four-digit code with repeats allowed has 10 × 10 × 10 × 10 = 10000 possibilities. That count is not a permutation.
The usual mistakes
Counting without order. 8 runners give 56 groups of three medal winners, but 336 results: each group of three can take the medals in 3! = 6 orders.
Multiplying n by r. Three medals from 8 runners is not 8 × 3 = 24; the first medal has 8 choices, the next 7 and the next 6.
Keeping n choices for every place. 8 × 8 × 8 = 512 would let one runner win all three medals.
A door code
In the application below, a code of four different digits is a permutation of 4 digits from 10. The codes with at least one repeated digit are then everything else.
Worked example: A Four-Digit Door Code, With and Without a Repeated Digit
Question An office door is opened by a four-digit code, and each digit can be any of 0 to 9. (a) How many codes have four different digits? (b) How many codes have at least one digit repeated?
1.With no rule, each of the four slots has 10 choices, so there are 10 × 10 × 10 × 10 = 10000 codes.
With no rule, each slot has 10 choices: 10 × 10 × 10 × 10 = 10000 codes. 2.With four different digits, the first slot has 10 choices. The second cannot repeat the first, so it has 9; the third has 8 and the fourth 7.
With four different digits, each slot has one choice fewer than the slot before it. 3.(a) Multiply the choices: 10 × 9 × 8 × 7 = 5040 codes. This is the number of permutations of 4 digits from 10, 10P4 = 10!6!.
(a) 10 × 9 × 8 × 7 = 5040 codes. 4.(b) Every code either has four different digits or repeats at least one digit, so at least one repeat is 10000 − 5040 = 4960 codes. Check: 5040 + 4960 = 10000.
(b) At least one repeat is all codes minus all different: 10000 − 5040 = 4960.
Answer: (a) 5040 codes; (b) 4960 codes
Common mistakes
- Counting four different digits as 104 = 210. The code 1234 and the code 4321 open different doors, so the order matters and the count is a permutation, not a combination.
- Counting (b) directly as a single case, such as 10 × 1 × 10 × 10 for a first digit repeated. Repeats can happen in many places and more than once, so the complement is the reliable count.