A permutation puts every item in order. Very often only some of them are needed: three medals for eight runners, a president and a treasurer chosen from a club, a four-digit code from ten digits. Choosing k items out of n and putting them in order is called an arrangement. This chapter introduces the slot method, the most reliable tool for this kind of count, derives the formula for arrangements with and without repetition, and gives a simple test for the question that decides almost every counting problem: does the order matter?
By the end you can
- Use the slot method: one box per position, the number of options in each, restricted boxes first.
- Count arrangements of k out of n items, with the formula n!/(n − k)! and without it.
- Count sequences with repetition allowed, nᵏ.
- Decide whether order matters with the swap test.
- Solve digit problems with restrictions, splitting into cases when needed.
Draw one box (slot) for each position of the result. Write in each box the number of options for that position at the moment it is filled. Multiply the boxes. That is all: the multiplication principle written in a way you can see. The method has one rule that matters: fill the boxes in an order where every box has a fixed number of options. In practice that means the restricted boxes first.
One box per position; the number in a box is how many options that position has at the moment it is filled. Multiply the boxes. The small number above a box is the order in which it is filled: the box with a restriction goes first, so the count in every later box is the same whatever was put before. When the restriction cannot be handled that way (is the last digit 0 or not?), split into cases, one row each, and add the rows.
In the figure, choose "even, 3 different digits". Whether the last digit is 0 changes how many options the first digit has (0 is forbidden there, but if 0 is already used at the end, all of 1 to 9 remain). No single filling order makes every box fixed, so the problem splits into two cases, each counted by slots, and the cases add: 72 + 256 = 328. Splitting into cases is the answer whenever one restriction affects another.
Eight runners race and gold, silver and bronze are given. Three boxes: 8 options for gold, 7 for silver (anyone but the winner), 6 for bronze: 8 · 7 · 6 = 336 podiums. The product starts at n and has k factors, one per box, each one less than the one before. This count is called a simple arrangement of n items taken k at a time, written A(n, k), Aₙ,ₖ or P(n, k). To write it with factorials, multiply and divide by the missing tail 5 · 4 · 3 · 2 · 1 = 5!.
When an item may be used again, every box has all n options. A PIN of 4 digits: 10 · 10 · 10 · 10 = 10⁴ = 10 000. A string of 8 bits, each 0 or 1: 2⁸ = 256. A 3-letter code with repeats: 26³ = 17 576. These are arrangements with repetition, and their count is a power.
| Code | repeats allowed | no repeats |
|---|---|---|
| 4 digits | 10⁴ = 10 000 | 10 · 9 · 8 · 7 = 5040 |
| 3 letters | 26³ = 17 576 | 26 · 25 · 24 = 15 600 |
| 6 lowercase letters | 26⁶ = 308 915 776 | 26 · 25 · 24 · 23 · 22 · 21 = 165 765 600 |
The most common mistake in counting is to use an arrangement where a combination is needed, or the other way round. A test settles it. Take one result and swap two of its chosen items. If the swap gives a different result, order matters, and you are arranging. If it gives the same result, order does not matter, and you are choosing a group (a combination, the subject of the next chapter).
| Situation | Swap two of the chosen | Order matters? |
|---|---|---|
| gold and silver among 8 runners | the winner and the runner-up change: a different podium | yes: arrangement |
| 2 representatives of a class, equal roles | the same two people: the same pair | no: combination |
| president and treasurer of a club | the jobs change hands: a different board | yes: arrangement |
| 6 numbers on a lottery ticket | the same set of numbers: the same ticket | no: combination |
| a 4-digit PIN | 1234 and 2134 open different locks | yes: arrangement |
| 3 pizza toppings out of 10 | the same pizza | no: combination |
Questions about numbers formed with digits are the most frequent arrangement problems in exams. They combine three kinds of restriction: the first digit cannot be 0, the digits may have to be different, and the number may have to be even, odd, a multiple of 5 or within some range. The slot method with the restricted boxes first handles all of them.
Even numbers with different digits: two cases
Numbers above a bound
With the digits 1, 2, 3, 4, 5 and 6, no repeats, how many 3-digit numbers are greater than 400? The restriction sits in the first digit: 4, 5 or 6, 3 options. Then 5 and 4 options for the other two: 3 · 5 · 4 = 60. Multiples of 5 with the same digits: the last digit must be 5, 1 option; then 5 · 4 for the first two: 20.
Restrictions between people: at most one per couple
Ten couples form a club, and a board of president, secretary and treasurer is chosen, with at most one person from each couple. The jobs are different, so order matters: three boxes. President: any of the 20 people. Secretary: not the president, and not the president's partner, 20 − 2 = 18. Treasurer: not the two people already chosen and not their two partners, 20 − 4 = 16. Total 20 · 18 · 16 = 5760. Each choice removes a whole couple from the options left.
1. A class of 30 elects a representative and a deputy: A(30, 2) = 30 · 29 = 870 possible results.
2. A 5-question multiple-choice test with options A to E: every way of answering is a sequence of 5 letters with repetition, 5⁵ = 3125.
3. Four-digit numbers with all digits different that are odd: last digit odd, 5 options; first digit not 0 and not the last, 8; then 8 and 7 for the middle: 8 · 8 · 7 · 5 = 2240.
4. A horse race with 12 horses, a bet on the first three in order: A(12, 3) = 12 · 11 · 10 = 1320 possible bets.
5. Three different flags are hoisted on 5 flagpoles in a row, at most one per pole, and the order on the poles matters: A(5, 3) = 60 signals.
| Wrong | Right | Why |
|---|---|---|
| 2 equal representatives from 30: 30 · 29 | 30 · 29/2 = 435 | swapping two representatives gives the same pair; the swap test says combination |
| 4-digit PIN: 10 · 9 · 8 · 7 | 10⁴ | digits in a PIN may repeat |
| even 3-digit numbers, distinct digits: 9 · 8 · 5 | 72 + 256 = 328 | whether the last digit is 0 changes the first digit's options; split into cases |
| A(8, 3) = 8!/3! | 8!/5! | divide by the factorial of the items NOT used, (n − k)! |
| board from 10 couples: 20 · 19 · 18 | 20 · 18 · 16 | each choice also removes that person's partner |
A round of 10 questions
Answer as many as you can. Mistakes come back at the end for a review round.
Every exercise is made on the spot, so a new round is never the same. The computer picks the answer first and builds the question around it, working with exact fractions, so the answer key is always right. Answers are read exactly: 0.75, 3/4 and 6/8 count as the same number (where lowest terms are asked for, 6/8 just gets a reminder). A wrong answer shows the worked solution line by line, in the order the lesson does it; the new number in each line is coloured.
Key ideas
- Slot method: one box per position, the options in each, multiply; restricted boxes first.
- When a restriction changes another box's options, split into cases and add them.
- Simple arrangements: A(n, k) = n(n − 1)…(n − k + 1) = n!/(n − k)!.
- With repetition allowed every box keeps all n options: nᵏ.
- Swap test: if swapping two chosen items gives a new result, order matters.