Arrangements and factorials
Eight different flags are hung one above another on a pole. How many orders are there, and why does the count grow so fast when one more flag is added?
Where you are 10 in Counting
Why this exists
People line things up all the time: books on a shelf, runners in a relay, songs in a playlist, flags on a pole. Each time the same question comes up. If every one of the objects is used exactly once, in how many different orders can they go?
The fundamental counting principle already answers it: fill the places one at a time and multiply. With every object used, the product runs all the way down to 1, and the same shape of product turns up so often that it has its own name and symbol, the factorial. This lesson is about that one product: what it counts, why 0! has to be 1, how quickly it grows, and what changes when the objects sit round a circle instead of in a row.
Definition
An arrangement of a set of different objects is a way of putting all of them in a row, so that each object is used exactly once and the order matters. Another name for an arrangement is a permutation of the set. The objects must be different from one another, the way the elements of a set are.
For a positive whole number n, n factorial is the product of the whole numbers from n down to 1:
So 1! = 1, 2! = 2 \times 1 = 2, 3! = 3 \times 2 \times 1 = 6 and 4! = 4 \times 3 \times 2 \times 1 = 24. Zero factorial is defined to be
and the reasons for that choice are in “Why it is true” below. The factorial is defined only for the whole numbers 0, 1, 2, 3 and so on.
Intuition
Picture empty places in a row, one for each object, and fill them from the left. With the three letters A, B and C, any of the 3 letters can go first. Whichever went first, 2 letters are left for the second place, and then exactly 1 for the last. The tree shows every way that can go.
Each path from the starting dot to an end is one order, and the tree has 3 \times 2 \times 1 = 6 ends. With n objects the first place has n choices, the next n - 1, and so on down to the last place, which has 1. That product is n!.
How fast it grows
Each factorial is the one before it multiplied by the next whole number, so the multiplier keeps getting bigger.
| n | n! | n | n! |
|---|---|---|---|
| 0 | 1 | 6 | 720 |
| 1 | 1 | 7 | 5{,}040 |
| 2 | 2 | 8 | 40{,}320 |
| 3 | 6 | 9 | 362{,}880 |
| 4 | 24 | 10 | 3{,}628{,}800 |
| 5 | 120 |
Doubling at every step gives 2^n, which also grows quickly, but from n = 4 on the factorial is ahead (4! = 24 against 2^4 = 16) and only pulls further away, because every later step multiplies n! by 5, 6, 7 and more while 2^n is still multiplied by 2. Even 10^n, which gains a zero at each step, is overtaken: n! is larger than 10^n for every n from 25 on. A standard pack of 52 playing cards can be put in 52! orders, a number with 68 digits.
Round a circle
When people sit round a round table, only who sits next to whom matters, not which chair anyone has. Turning everyone one seat round gives the same seating, as the four drawings show.
Results
Arrangements in a row. The number of arrangements of n different objects in a row is
Each factorial from the one before. For every whole number n \ge 1,
Zero factorial. 0! = 1. There is exactly one arrangement of an empty set: the empty row.
Arrangements round a circle. If n \ge 1 different objects are placed round a circle and two placements count as the same when one is a turn of the other, the number of arrangements is
Why it is true
Arrangements in a row. Fill the n places one at a time from the left. The first place can take any of the n objects. Whatever went there is used up, so the second place has n - 1 choices, and this number is the same whichever object went first. The third place has n - 2, and so on, until the last place has exactly 1 object left. By the fundamental counting principle the number of arrangements is the product n \times (n - 1) \times \cdots \times 1 = n!.
Every arrangement is counted exactly once: two different sequences of choices put a different object in some place, so they give different rows, and every row comes from the sequence of choices that reads it from the left.
Each factorial from the one before. In n! = n \times (n - 1) \times \cdots \times 1, the factors after the first are exactly the product that defines (n - 1)!. Grouping them together, which the associative property of multiplication allows, gives n! = n \times (n - 1)!. The same fact read as counting: choose the object for the first place in n ways, then arrange the other n - 1 in (n - 1)! ways.
Zero factorial. The definition n! = n \times (n-1) \times \cdots \times 1 says nothing when n = 0, because there is no list of factors from 0 down to 1. Two separate reasons fix the value at 1.
- The rule n! = n \times (n - 1)! holds for every n \ge 2. Asking it to hold at n = 1 as well gives 1! = 1 \times 0!, and since 1! = 1, the only possible value is 0! = 1.
- An arrangement of 0 objects is a row with nothing in it. There is exactly one such row, so the count of arrangements, which is n! for every other n, should be 1 here too.
A product with no factors at all is given the value 1 for the same reason: multiplying by it must change nothing.
Round a circle. Take any arrangement of n objects round a circle and read it clockwise starting from one of the n seats. That gives a row of all n objects, and starting at each of the n seats in turn gives n different rows. Every row arises this way from exactly one circular arrangement: sit the row round the table in order. So the n! rows fall into groups of n, one group for each circular arrangement, and the number of circular arrangements is
A second way to see it: since turning the table changes nothing, sit one chosen object down first, anywhere. Every other seat is now fixed by its position relative to that object, so the remaining n - 1 objects fill n - 1 distinct seats, in (n - 1)! ways.
Worked examples
Flags on a pole
Eight different flags are hung in a row, one above another, on a pole.
(a) In how many orders can they be hung?
(b) A ninth flag, different from the others, is added. How many orders are there now?
Solution(a) Fill the pole from the top. The top place can take any of the 8 flags, the place below it any of the 7 that are left, and so on down to the bottom place, which takes the last flag. Every flag is used once, so the count is a factorial:
(b) Nine flags give 9! orders. Rather than multiply from scratch, use 9! = 9 \times 8!:
As counting: the new flag can go into any of 9 positions in each of the 40{,}320 old orders (above the top flag, between any two, or below the bottom one), and each new order comes from exactly one old order and one position. One more flag multiplied the count by 9, not by 2.
Quotients of factorials
Simplify without working out any factorial in full.
(a) \dfrac{10!}{7!}
(b) \dfrac{12!}{10! \times 2!}
(c) \dfrac{(n + 1)!}{(n - 1)!} for a whole number n \ge 1
Solution(a) Write 10! only as far down as 7!, using n! = n \times (n-1)! three times: 10! = 10 \times 9 \times 8 \times 7!. The 7! then cancels:
(b) In the same way 12! = 12 \times 11 \times 10!, and 2! = 2:
(c) Here (n + 1)! = (n + 1) \times n \times (n - 1)!, so
Check for (c) with n = 3: \dfrac{4!}{2!} = \dfrac{24}{2} = 12, and (3 + 1) \times 3 = 12.
How many books?
Clemency finds that the books on one of her shelves can be arranged in 720 different orders. All the books are different.
(a) How many books are on the shelf?
(b) Could a shelf of different books have exactly 1{,}000 arrangements?
Solution(a) If there are n books, then n! = 720. Undo the factorial by dividing by 2, then 3, then 4 and so on, since n! is built by multiplying by those numbers in turn:
Reaching 1 after dividing by 6 means 720 = 6 \times 5 \times 4 \times 3 \times 2 \times 1 = 6!, so there are 6 books.
(b) No. The factorials grow without skipping back: 6! = 720 and the next is 7! = 7 \times 720 = 5{,}040. Every number of different books gives a factorial, and 1{,}000 lies strictly between two neighboring factorials, so it is not one of them.
Running the rule backwards
Use n! = n \times (n - 1)!, read as (n - 1)! = \dfrac{n!}{n}, to find 3!, 2!, 1! and 0! from 4! = 24, then explain why the same step cannot give a value for (-1)!.
SolutionEach step down divides by the number just left behind:
The pattern lands on 0! = 1, matching the definition. One more step would need (-1)! = \dfrac{0!}{0}, a division by zero. Put the other way round, the rule at n = 0 would say 0! = 0 \times (-1)!, so 1 = 0 \times (-1)!, and no number times 0 gives 1. The factorial stops at 0.
Six at a round table
Six friends sit down to dinner at a round table with six identical chairs. Two seatings count as the same if everyone has the same person on their left and the same person on their right.
(a) How many seatings are there?
(b) How many more ways are there to seat the six friends on six chairs in a straight row?
Solution(a) Turning the whole table keeps every pair of neighbors, so seatings that differ only by a turn count once. Seat one friend, Leofric say, anywhere: with the chairs identical, where he sits makes no difference. The other 5 friends now fill the 5 chairs counted clockwise from Leofric, each a different chair, in 5! ways:
(b) In a row, the order from left to right is all that matters, so there are 6! = 720 ways, and 720 - 120 = 600 more than round the table. Each round-table seating can be cut open at any of its 6 places to make a row, and 720 = 6 \times 120.
Check that the left and right neighbors really are fixed. In the seating read clockwise as Leofric, then five friends in some order, a turn by one chair leaves every friend with the same two neighbors, which is why the 6 turns count as one.
Listing every order
A computer program lists every order of a set of objects, one order per line, at a million lines a second.
(a) How long does it take for 15 objects?
(b) How long for 20 objects?
Solution(a) There are 15! = 1{,}307{,}674{,}368{,}000 orders. At 10^6 a second that is about 1{,}307{,}674 seconds. A day has 24 \times 60 \times 60 = 86{,}400 seconds, and
so the list takes a little over 15 days.
(b) There are 20! = 2{,}432{,}902{,}008{,}176{,}640{,}000 orders, which takes about 2{,}432{,}902{,}008{,}177 seconds. A year of 365.25 days has 365.25 \times 86{,}400 = 31{,}557{,}600 seconds, so
which is about 77{,}000 years. The five extra objects multiplied the work by 20 \times 19 \times 18 \times 17 \times 16 = 1{,}860{,}480. This is why arrangement problems are counted, never listed.
Keeping the kinds together
Four different math books and three different novels go on a shelf. The math books must stand next to one another, and so must the novels. How many arrangements are there?
SolutionThink of the shelf in two stages. First, the two kinds form two blocks, and the blocks can stand in 2! orders: math then novels, or novels then math. Second, whichever order the blocks are in, the four math books can be arranged inside their block in 4! ways and the three novels inside theirs in 3! ways. The number of ways at each stage does not depend on the earlier choices, so the fundamental counting principle multiplies them:
Check that nothing is counted twice. Any such shelf shows which kind comes first, the order of the math books and the order of the novels, and those three facts rebuild the shelf exactly, so each shelf comes from one choice at each stage. Without the rule there would be 7! = 5{,}040 arrangements, so only 288 of them keep both kinds together.
Boundaries
Every object must be used, exactly once. The factorial counts orders of a whole set. Putting only some of the objects in order, such as 3 of 10 paintings hung in a row of three frames, stops the product part-way down; that is the count of permutations.
The objects must all be different. If some are identical, n! counts the same row more than once. The letters A, B, B can be written in only 3 different ways (ABB, BAB, BBA), not 3! = 6: swapping the two B’s gives the same row, so each row was counted 2! = 2 times.
The factorial is defined for whole numbers only. n! means something for n = 0, 1, 2, 3 and so on. There is no (-1)!, as the backwards rule showed, and no \left(\tfrac{1}{2}\right)! in this sense, since there is no list of factors to multiply.
Round a circle, only turns count as the same. The count (n - 1)! treats two seatings as equal when one is a turn of the other. A mirror image is still different: clockwise A, B, C, D is not clockwise A, D, C, B. If the arrangement can be turned over as well, like beads on a loop of string, each arrangement of n \ge 3 objects has been counted twice and the count is \dfrac{(n - 1)!}{2}. And if the seats themselves are different (one chair at the head of the table, or numbered places), turns are no longer the same and the count is back to n!.
Where this goes next
Stopping the factorial part-way down counts ordered choices of only some of the objects, the permutations, written as a quotient of factorials like the ones in the second example. Dividing that count by the orders that do not matter gives combinations, whose values fill Pascal’s triangle and are the coefficients in the binomial theorem. When one object has to go in one particular place, such as a given person at the end of a row, the place with the rule is filled first; that is counting with a restriction. The idea that identical objects are counted more than once also returns there, and in inclusion and exclusion the factorial counts the orders that leave no object in its starting place. The whole family lives under counting.
Exercises
Working with factorials
- Find 6! and 7!.
- Simplify \dfrac{9!}{7!}.
- Simplify \dfrac{11!}{9! \times 2!}.
- Find 0! + 1! + 2! + 3!.
- Simplify \dfrac{n!}{(n - 2)!} for a whole number n \ge 2.
- Simplify \dfrac{(n + 2)!}{n!} for a whole number n \ge 0.
Arranging in a row
- In how many orders can seven different books stand on a shelf?
- In how many orders can the five letters of the word FOCAL be written, each used once?
- Four speakers each give one talk at a meeting, one after another. In how many orders can they speak?
- Eleven guests arrive at a party one at a time. In how many orders can they arrive?
- A baker sets 6 different cakes in a row in a shop window. How many orders are possible? How many if a seventh cake is added to the row?
Round a circle
- Five people sit at a round table with five identical chairs. How many seatings are there, if seatings that differ only by a turn of the table count as the same?
- Eight children hold hands in a ring for a game. How many different rings are there, if two rings count as the same when every child has the same neighbor on the left and on the right?
- Seven people can sit on seven chairs in a row or round a round table with seven identical chairs. How many more seatings are there in the row?
Size and growth
- Find n if n! = 3{,}628{,}800.
- Find n if \dfrac{n!}{(n - 1)!} = 12.
- Find the smallest whole number n for which n! is larger than 1{,}000{,}000.
- How many zeros does 10! end in?
Putting arrangements together
- Two different pens and five different pencils lie in a row on a desk, with the pens next to each other and the pencils next to one another. How many arrangements are there?
- Clemency hangs five different photographs in a row and three more different photographs in a row underneath. How many ways are there to hang all eight?
Reasoning
- Explain, by counting arrangements, why n! = n \times (n - 1)! for every whole number n \ge 1.
- Explain why 0! is defined to be 1, and why the same reasoning gives no value for (-1)!.
- Explain why n different people can sit round a round table in (n - 1)! ways, and check the formula with n = 3 by listing the seatings.
- Explain why n! ends in at least one zero for every n \ge 5.
- Explain why n! > 2^n for every whole number n \ge 4.
Answers
- 6! = 720 and 7! = 7 \times 720 = 5{,}040.
- 72. Since 9! = 9 \times 8 \times 7!, the quotient is 9 \times 8 = 72.
- 55. Since 11! = 11 \times 10 \times 9!, the quotient is \dfrac{11 \times 10}{2} = \dfrac{110}{2} = 55.
- 10. The terms are 1 + 1 + 2 + 6 = 10, with 0! = 1.
- n(n - 1). Since n! = n \times (n - 1) \times (n - 2)!, the (n - 2)! cancels. For example, \dfrac{6!}{4!} = 30 = 6 \times 5.
- (n + 2)(n + 1). Since (n + 2)! = (n + 2) \times (n + 1) \times n!, the n! cancels. For example, \dfrac{5!}{3!} = 20 = 5 \times 4.
- 7! = 5{,}040 orders.
- 5! = 120 orders. The letters F, O, C, A, L are all different.
- 4! = 24 orders.
- 11! = 39{,}916{,}800 orders.
- 6! = 720 orders; with a seventh song, 7! = 7 \times 720 = 5{,}040.
- (5 - 1)! = 4! = 24 seatings.
- (8 - 1)! = 7! = 5{,}040 rings. Fix one child; the other 7 fill the places round from that child.
- 4{,}320 more. In a row 7! = 5{,}040; round the table 6! = 720; and 5{,}040 - 720 = 4{,}320.
- n = 10. Dividing 3{,}628{,}800 by 2, 3, \ldots, 10 in turn reaches 1 at 10, so 3{,}628{,}800 = 10!.
- n = 12. The quotient \dfrac{n!}{(n - 1)!} is n, so n = 12.
- n = 10. 9! = 362{,}880 is smaller than 1{,}000{,}000, and 10! = 3{,}628{,}800 is larger.
- 2 zeros: 10! = 3{,}628{,}800. The factors 10 and 2 \times 5 each give one factor of 10.
- 480. The two blocks go in 2! orders, the pens in 2! and the pencils in 5!: 2 \times 2 \times 120 = 480.
- 720. The top row can be hung in 5! = 120 ways and, whatever it is, the bottom row in 3! = 6 ways: 120 \times 6 = 720.
- To arrange n objects, first choose the object for the first place, in n ways. Whatever it is, the other n - 1 objects fill the remaining places in (n - 1)! ways. By the fundamental counting principle there are n \times (n - 1)! arrangements, and there are also n!, so the two are equal.
- Asking n! = n \times (n - 1)! to hold at n = 1 gives 1 = 1 \times 0!, so 0! = 1; and the empty set has exactly one arrangement, the empty row. At n = 0 the same rule would say 1 = 0! = 0 \times (-1)!, but 0 times any number is 0, so no value of (-1)! works.
- Seat one person anywhere; since the table can be turned, where makes no difference. The other n - 1 people then fill the n - 1 seats counted clockwise from that person, in (n - 1)! ways. For n = 3 with A seated: clockwise A, B, C or A, C, B, two seatings, and (3 - 1)! = 2.
- For n \ge 5 the product n! contains both 2 and 5 as factors, so it is a multiple of 2 \times 5 = 10, and every multiple of 10 ends in 0.
- At n = 4, 4! = 24 > 16 = 2^4. Going from n to n + 1 multiplies n! by n + 1, which is at least 5, and multiplies 2^n by only 2. So if n! > 2^n, then (n + 1)! = (n + 1) \times n! > 2 \times 2^n = 2^{n+1}, and the inequality passes on from each n to the next, starting at 4.