A permutation is an ordering of all the items of a group: the order of runners crossing the line, of books on a shelf, of letters in a word. Counting permutations is the multiplication principle applied to one special situation, every item used exactly once, and it leads to one of the most important numbers in mathematics, the factorial. This chapter defines the factorial and learns to handle it by hand, counts permutations, and then adds the three complications that exams love: conditions on where items may stand, items that repeat, and items sitting in a circle.
By the end you can
- Compute factorials and simplify quotients of factorials without multiplying them out.
- Count the orders of n different items, and explain why there are n! of them.
- Handle conditions: fixed places, items kept together or apart, one item before another.
- Count anagrams of a word with repeated letters by dividing out the repeats.
- Count arrangements around a round table, and say why the answer is (n − 1)!.
In how many orders can 5 different books stand on a shelf? Fill the shelf from left to right. Any of the 5 books can go first. Whichever it was, 4 remain for the second place, then 3, then 2, and the last book goes into the last place: 5 · 4 · 3 · 2 · 1 = 120. A product of every whole number from n down to 1 appears so often that it has its own name and symbol: n factorial, written n!.
| n | 0 | 1 | 2 | 3 | 4 | 5 | 6 | 7 | 8 | 10 |
|---|---|---|---|---|---|---|---|---|---|---|
| n! | 1 | 1 | 2 | 6 | 24 | 120 | 720 | 5040 | 40 320 | 3 628 800 |
Why 0! = 1
0! is defined as 1, and this is not an arbitrary choice. Two independent reasons give the same value. The rule n! = n · (n − 1)! read backwards says (n − 1)! = n!/n: going down the table divides by the n you leave. Following it down to the bottom gives 0! = 1!/1 = 1. And as a count, there is exactly one way to arrange no items at all: do nothing. With 0! = 1 every formula of this section also works in its edge cases.
Simplifying quotients of factorials
Factorials are huge, but quotients of factorials are usually small, because most of the factors cancel. Never compute both factorials and divide: write the bigger one down only as far as the smaller one, then cancel.
The factorial grows faster than any power. 10! is already over three million, 20! is about 2.4 · 10¹⁸, and a deck of 52 cards can be shuffled into 52! ≈ 8 · 10⁶⁷ orders. That is why a well-shuffled deck is almost certainly in an order that no deck in history has ever been in.
An ordering of all n items of a group, each used exactly once, is a simple permutation of those items. The shelf argument works for any n: n options for the first place, n − 1 for the second, down to 1 for the last. So there are n! permutations. The symbol P with the number of items below is common in Brazilian textbooks: P₅ = 5! = 120.
A classic use: anagrams. An anagram of a word is any ordering of its letters, whether it means something or not. The word AMOR has 4 different letters, so it has P₄ = 4! = 24 anagrams: AMOR, AMRO, AOMR, and so on, including ROMA. The word LIVRO has 5 different letters: 5! = 120 anagrams.
Exam problems rarely ask for all the orders; they add a condition. Each kind of condition has a standard way in, and all of them are the multiplication principle with the restricted part handled first.
Items in fixed places
How many anagrams of LIVRO start with a vowel? Fill the restricted place first: the first letter is I or O, 2 options. The other 4 letters fill the remaining 4 places in any order: 4! = 24. Total 2 · 24 = 48. Start with a vowel and end with a consonant: first place 2 options, last place 3 (L, V, R), middle 3! = 6: 2 · 3 · 6 = 36.
Items that must stay together: the block
Six friends stand in a row for a photo, and two of them, a couple, want to stand side by side. Glue the couple into one block. Now there are 5 things to arrange, the block and the 4 others: 5! = 120. Inside the block the couple can stand in 2! = 2 orders. Total 120 · 2 = 240. In general, a block of m items that must stay together among n items gives (n − m + 1)! · m!.
Items that must stay apart: total minus together
If the couple must not stand side by side, count the opposite. All orders: 6! = 720. Orders with the couple together: 240. Every order is one or the other, so 720 − 240 = 480 orders have them apart. Counting what you do not want and subtracting it from the total is called counting by the complement, and it is often the shortest way.
One item before another: symmetry
In how many orders of the 6 friends does Ana stand somewhere to the left of Bia, not necessarily next to her? Swap the two in any order and you get an order where Bia is to the left of Ana. This swap pairs the orders up perfectly, so exactly half of them have Ana first: 720/2 = 360. With three people who must appear in a given order among themselves, divide by 3! = 6.
Alternating rows
3 boys and 3 girls stand in a row, alternating boy and girl. The pattern is either B G B G B G or G B G B G B: 2 cases. In each, the boys fill their 3 places in 3! = 6 ways and the girls theirs in 3! = 6 ways. Total 2 · 6 · 6 = 72.
How many anagrams does BANANA have? It has 6 letters, so 6! = 720 if they were all different. But they are not: there are three A's and two N's. Swapping two A's gives back the same word, so 720 counts each real word several times. The way out is to pretend the repeated letters are different by numbering them, count, and then divide out the numbering.
Each chip is one different word made from the same letters. Number the repeated letters (A₁, A₂, A₃) as if they were different: then there are n! orders, but each real word appears once for every way of numbering its repeats. The panel below shows those copies for the selected word; their number is the same for every word, so n! divided by it gives the number of chips. Click a word to see its numbered copies.Tap a word to see its numbered copies.
The same formula counts shortest paths on a grid. To walk from one corner of a street grid to the corner 4 blocks east and 3 blocks north, always going east (E) or north (N), every route is a word of 7 moves with four E's and three N's, like EENENNE. So the number of shortest routes is 7!/(4! · 3!) = 35. A route that must pass through a given corner is two such walks, one after the other: multiply them.
Around a round table, what matters is who sits next to whom, not which chair is "first". If everybody stands up and moves one chair to the left, the seating has not really changed. So each real seating was counted n times among the n! orders of a row, once for each turn. Equivalently: fix one person's chair to remove the turning, and arrange the other n − 1 people in the remaining chairs, as in a row.
1. Eight athletes in a final: the number of possible orders at the finish line, with no ties, is 8! = 40 320.
2. Anagrams of ESCOLA that start with S: S is fixed in the first place and the other 5 letters are free: 5! = 120.
3. Anagrams of ARARA: 5 letters, three A's and two R's: 5!/(3! · 2!) = 120/12 = 10.
4. Seven books on a shelf, the 3 maths books together in any order: block of 3 plus 4 other books, 5 things: 5! · 3! = 120 · 6 = 720.
5. Five children play a round game holding hands in a circle: (5 − 1)! = 24 different circles.
| Wrong | Right | Why |
|---|---|---|
| 0! = 0 | 0! = 1 | there is one way to arrange nothing, and it keeps n! = n · (n − 1)! true for n = 1 |
| 10!/5! = 2! | 10 · 9 · 8 · 7 · 6 = 30 240 | factorials do not divide like the numbers inside them; cancel the common tail |
| BANANA: 6! = 720 anagrams | 6!/(3! · 2!) = 60 | swapping identical letters gives the same word; divide out the repeats |
| couple together: 5! = 120 | 5! · 2! = 240 | the two inside the block can also swap |
| 6 people at a round table: 6! = 720 | 5! = 120 | turning everyone together is the same seating |
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
- n! = n · (n − 1) · … · 1, and n! = n · (n − 1)!; 0! = 1.
- Quotients of factorials cancel: write the larger only down to the smaller.
- n different items have Pₙ = n! orders.
- Fixed places first; a block that stays together counts as one item, times its inner orders; "apart" is total minus together.
- Repeated items: divide n! by the factorial of each repeat count.
- Around a round table with identical chairs: (n − 1)!.