Put n different things in a row in n! ways, pick k of them in order in n!/(n - k)! ways, and see why 0! = 1. Worked on five items, with 120 orders and 60 ordered picks of three, and on why no computer can try every order of a shuffled data set.
Count the orders of n different items as n factorial with the multiplication principle, and work out small factorials by hand.
Count the ordered picks of k items from n different items as n!/(n - k)!, and explain the cancellation that gives the formula.
Explain in two ways why 0! = 1: as an empty product, and from the formula for ordered picks.
Compare the growth of n! with that of 2^n, and say why trying every order of a large data set is hopeless.
In review. The maths and code on this page are checked by automated tests on every change, but an independent reader has not signed it off yet. Spot a mistake or a confusing step? Tell us.
The question
Before each pass through the training data, the examples are usually shuffled, so that the model meets them in a fresh order every time. Take a small data set of 20 examples. How many different orders could the shuffle produce, and could a computer ever try them all?
From the last lesson
1. How many strings of 8 bits are there?
Show answer
\({2^8 = 256}\): two options for each of 8 places.
2. When is the size of \({A \cup B}\) simply \({\abs{A} + \abs{B}}\)?
Show answer
When \(A\) and \(B\) are disjoint, that is, \({A \cap B}\) is empty. Otherwise the size of the overlap must be subtracted once.
Intuition
Take three letters, a, b and c, and put them in a row. The first place can hold any of the 3. Once it is filled, that letter is used up, so the second place has only 2 left. The third place takes whatever remains: 1 letter. Draw the choices as a tree, one branch for every option.
M01.8.2-F1
Arranging a, b and c. Three choices for the first place, then two left, then one: the tree has six paths, one for each order.
This is the multiplication principle of lesson M01.8.1 with one change. In a string every place could hold any symbol, so the number of options stayed the same at each stage. Here each choice uses up a letter, so the number of options drops by one at each stage: 3, then 2, then 1, which makes six orders. Each arrangement of all the items in a row is called a permutation of them.
Build it up
Step 1. All the items in a row. With \(n\) different items, the first place has \(n\) options, the second has \({n - 1}\), and so on down to 1 option for the last place. The product of the whole numbers from \(n\) down to 1 is \(n\) factorial, written \(n!\), which lesson M01.7.4 met as a product:
The first few are \({1! = 1}\), \({2! = 2}\), \({3! = 6}\), \({4! = 24}\) and \({5! = 120}\). So the course’s five items, a, b, c, d and e, can stand in a row in 120 orders.
Step 2. Only some of the places. Now fill only 3 places from the 5 items: a gold, a silver and a bronze medal for 3 of 5 runners, say. The options go 5, then 4, then 3, and then the choosing stops. So the number of ordered picks of three is
\[
5 \times 4 \times 3 = 60.
\]
In general, \(k\) places filled from \(n\) items give \(k\) factors that fall by one each time, starting at \(n\). The \(k\)th place comes after \({k - 1}\) items have been used up, so the last factor is
\[
n - (k - 1) = n - k + 1.
\]
Step 3. The same count with factorials. The product of 5, 4 and 3 is the beginning of \(5!\) without its tail \({2 \times 1}\), which is \(2!\). So dividing \(5!\) by \(2!\) removes the tail and leaves exactly the product we want:
The tail is what is left of \(5!\) after the 3 factors we want, so it has \({5 - 3 = 2}\) factors. With \(k\) places the tail is \({(5 - k)!}\), and the count is \(5!\) divided by it.
Step 4. Why \(0!\) is 1. Use all 5 places: the ordered picks of five are the 120 orders, and the tail has \({5 - 5 = 0}\) factors, so the count is \(5!/0!\). That is right only if \({0! = 1}\). The same answer comes from lesson M01.7.4: \(0!\) multiplies no numbers at all, and a product of no numbers, an empty product, is 1. It also fits the counting: there is exactly one way to arrange nothing, the empty row.
Step 5. How fast factorials grow. Each new item multiplies the number of orders by a bigger number than the last. Compare the \(2^n\) subsets of the last lesson, which only double at each step.
M01.8.2-F3
The number of orders, \(n!\), against the number of subsets, \(2^n\), on a log scale, where each step up multiplies by 1,000. The factorial is behind for 1, 2 and 3 items and then pulls away for good.
For 1, 2 and 3 items the power of two is ahead. From \({n = 4}\) on the factorial wins, because from then on it multiplies by 5, 6, 7, … at each step while \(2^n\) only doubles. By \({n = 20}\) the factorial is more than two million million times larger.
The formal statement
NoteDefinition: factorial
For a whole number \({n \ge 1}\),
\[
n! = 1 \times 2 \times \cdots \times n,
\]
read “\(n\) factorial”. Also \({0! = 1}\).
Each factorial is the one before it times one more number. For \({n \ge 1}\),
\[
n! = n \times (n-1)!.
\]
With \({n = 1}\) it says that \(1!\) is \({1 \times 0!}\), which agrees with \({0! = 1}\).
NoteResult: orders and ordered picks
Let \(n\) different items be given.
They can be put in a row in \(n!\) orders.
For each whole number \(k\) from 0 to \(n\), the number of ways to pick \(k\) of them in order, with no item used twice, is \(\dfrac{n!}{(n-k)!}\).
Why the first. Fill the places one at a time. The multiplication principle applies, because at each stage the number of options does not depend on which items were used, only on how many: \(n\), then \({n - 1}\), and so on down to 1. Their product is \(n!\).
Why the second. The same stages, stopped after \(k\) places, give \(k\) falling factors: the first \(k\) factors of \(n!\). Now split \(n!\) into those \(k\) factors and the rest, which is \({(n - k)!}\):
Divide both sides by \({(n - k)!}\), and the \(k\) falling factors are left on their own. With \({k = n}\) the formula divides by \({0! = 1}\) and gives \(n!\), the first result again. If \(k\) is larger than \(n\) there is no way to fill the places at all, so the count is 0.
Many books give this count its own symbol, such as \(P(n, k)\); OpenStax writes \(P(n, r)\) or \({}_nP_r\). This course writes the fraction, which is also what Python’s math.perm(n, k) computes.
Worked example
Five items, a to e, three places. How many ordered picks of three are there, and how do the numbers of options fall?
M01.8.2-F2
Following one pick, c then a then e. At each place the letters already used are faded, so the number of options falls from 5 to 4 to 3.
The first place: all 5 letters. Say c is picked.
The second place: 4 letters left, because c is used up. Say a.
The third place: 3 letters left. Say e.
Whatever is picked, the numbers of options are 5, 4 and 3, so the number of ordered picks is
\[
5 \times 4 \times 3 = 60.
\]
Check with factorials:\(5!/2!\) is 120 divided by 2, which is 60 again. Compare with repeats allowed. If a letter could be used again, every place would have all 5 options: \({5^3 = 125}\) strings, as in lesson M01.8.1. The 65 extra strings are exactly those with a repeated letter, such as a, a, c.
Twenty examples. The number of orders of a data set of 20 examples is
about \({2.4329 \times 10^{18}}\). A computer that could check a billion orders every second would need more than 2,432,902,008 seconds to go through them all, which is about 77 years.
Code
First from scratch. Three loops, one for each place, and a test that skips any letter already used, list the orders of three items. A factorial is a running product.
items = ["a", "b", "c"]orders = []for first in items:for second in items:# Skip a letter that is used already.if second == first:continuefor third in items:if third in (first, second):continue orders.append(first + second + third)print(len(orders), orders)def factorial(n):# Start from the empty product, 1,# so that factorial(0) is 1. result =1# Multiply by k = 1, 2, ..., n.for k inrange(1, n +1): result = result * kreturn resultdef ordered_picks(n, k): result =1# The k falling factors n, n - 1, ...for i inrange(k): result = result * (n - i)return resultprint(factorial(0), factorial(3), factorial(5))print(ordered_picks(5, 3))
Now the library versions. itertools.permutations(items, k) lists the ordered picks one by one; math.perm(n, k) only counts them, and math.factorial(n) gives \(n!\).
import itertoolsimport math# Tuples such as ('c', 'a', 'e').picks =list(itertools.permutations("abcde", 3))print(len(picks), picks[:4])print(math.perm(5, 3), math.perm(5), math.perm(5, 6))print(math.factorial(5))
math.perm(5) with no second number is \(5!\), and math.perm(5, 6) is 0: there is no way to fill six places from five items. Last, the twenty examples, and the race between \(n!\) and \(2^n\).
orders_20 = math.factorial(20)# At a billion orders per second:seconds = orders_20 /1_000_000_000years = seconds / (365.25*24*3600)print(orders_20)print(round(years, 1), "years")n =1while math.factorial(n) <=2** n: n = n +1print("n! first beats 2^n at n =", n)print("20!/2^20 =", orders_20 //2**20)
2432902008176640000
77.1 years
n! first beats 2^n at n = 4
20!/2^20 = 2320196159531
Explore
The choose-and-arrange explorer of this module lives in lesson M01.8.3. Set 5 items and 3 places, with “order matters” on and “repeats allowed” off, and it lists all 60 ordered picks of the worked example. Then switch repeats on and watch the 60 grow to 125.
Pitfalls
M01.8.2-F4
Wrong beside right. Giving every place all five options counts picks that use an item twice; when each pick uses an item up, the options fall to 4 and then 3.
“Every place has all \(n\) options.”
Only if an item can be used again, as a letter can in a password. A runner cannot take two medals, and an example cannot appear twice in one order of a data set, so each choice uses an item up: 5, 4 and 3 options give 60, not the 125 of \(5^3\). Before multiplying, ask whether the options shrink.
“\(0!\) is 0, because there is nothing to multiply.”
A product with nothing in it is 1, not 0, for the same reason that a sum with nothing in it is 0: a running product starts at 1, and multiplying by nothing leaves it there. The formula for ordered picks needs \({0! = 1}\) too: if \(0!\) were 0, the count of all orders of five items, \(5!/0!\), would be a division by zero. In code, math.factorial(0) is 1.
“Any \(n\) things have \(n!\) orders.”
Only \(n\)different things. The letters a, a, b give only 3 different rows, aab, aba and baa, not \({3! = 6}\), because swapping the two a’s changes nothing. Each different row was counted twice, once for each order of the two a’s. Dividing out such repeats is exactly the idea of the next lesson.
Check yourself
Recall
1. What is \(5!\), and what does it count?
Show answer
\({5! = 120}\). It is the number of orders in which 5 different items can stand in a row.
2. In how many ways can gold, silver and bronze go to 3 of 5 runners?
Show answer
60: 5 choices for gold, then 4 for silver, then 3 for bronze.
3. Give two reasons why \({0! = 1}\).
Show answer
It is an empty product, and an empty product is 1. And the formula \({n!/(n - k)!}\) with \({k = n}\) must give the \(n!\) orders of all \(n\) items, which needs \({0! = 1}\). (A third: there is one way to arrange nothing.)
4. From which \(n\) on is \(n!\) larger than \(2^n\)?
Show answer
From \({n = 4}\) on: \({4! = 24}\) while \({2^4 = 16}\). Below that, \(1!\), \(2!\) and \(3!\) are smaller than 2, 4 and 8.
5. What do math.perm(5, 3) and math.perm(5, 6) return?
Show answer
60, the ordered picks of three from five, and 0, because six places cannot be filled from five items without using one twice.
Exercises
1.★ In how many orders can 6 different books stand on a shelf? In how many ways can a gold, a silver and a bronze medal go to 3 of 8 runners?
Show solution
The books: \({6! = 720}\) orders. The medals: 8 choices for gold, 7 for silver, 6 for bronze,
\[
8 \times 7 \times 6 = 336 = \frac{8!}{5!}.
\]
2.★★ How many strings of 4 letters can be made from the 26 letters of the alphabet, and how many of them have no repeated letter? What share of all the strings is that?
Show solution
With repeats allowed, \({26^4 = 456{,}976}\) strings (lesson M01.8.1). With no letter twice the options fall at each place:
so about 79 strings in 100 have no repeated letter.
3.★★★ A data set of 10 examples is shuffled. How many orders are there? How many of them put example 1 first? Divide the second number by the first, and explain the answer without any arithmetic.
Show solution
There are \({10! = 3{,}628{,}800}\) orders. If example 1 is first, the other 9 examples fill the 9 remaining places in \({9! = 362{,}880}\) orders. Since \(10!\) is \({10 \times 9!}\), the ratio is
Without arithmetic: each of the 10 examples is first in the same number of orders (swap the names of two examples and the orders match up one to one), so example 1 is first in exactly a tenth of them. A fair shuffle puts each example first one time in ten.
Summary card
Each place uses an item up, so the options fall by one at every step.
M01.8.2-F1
Three, then two, then one: six orders.
All \(n\) in a row.\(n!\) orders, the product of the numbers from 1 to \(n\).
\(k\) of \(n\) in order.\(\dfrac{n!}{(n-k)!}\) ordered picks: the first \(k\) factors of \(n!\).
Empty product.\({0! = 1}\).
Growth. From \({n = 4}\) on, \(n!\) is larger than \(2^n\); \(20!\) has 19 digits.
Sources and next steps
Sources. Each was opened and checked against this lesson on 12 November 2026.
Richard Hammack, Book of Proof, third edition, Section 3.4. Definition 3.1 defines \(n!\) with \({0! = 1}\) and warns that 0 is a common wrong value; Equation 3.1 is the rule from \({(n-1)!}\) to \(n!\); Fact 3.4 gives the ordered picks of \(k\) from \(n\) as the falling product and as \({n!/(n-k)!}\); the section also gives the value of \(20!\).
Jay Abramson and others, Algebra and Trigonometry 2e, Section 13.5 (OpenStax). The formula for permutations of \(n\) distinct objects taken \(r\) at a time, written \(P(n, r)\), and the use of \({0! = 1}\).
Frontier note: a shuffle that cannot reach most orders
Python’s random.shuffle draws on a generator, the Mersenne Twister, that repeats itself after \({2^{19937} - 1}\) steps. That is a huge number, but \(n!\) passes it at \({n = 2081}\), so a longer list has more orders than the generator’s period, and most orders can never come out. The documentation of random.shuffle says so and names 2080 as the largest length whose orders fit within that period. For training this does not matter, because no one needs every order, only orders with no pattern; but it shows how quickly \(n!\) outruns anything a machine can hold.
