Lining up for a photo#
Three friends, Ana, Ben and Cai, line up for a photo. How many different line-ups are there?
Fill the spots from left to right. The first spot can be any of the 3. Once it is filled, 2 people remain for the second spot. Then 1 person is left for the last spot. So there are 3 · 2 · 1 = 6 line-ups.
Written with letters: ABC, ACB, BAC, BCA, CAB, CBA. Six, as promised.
That “fill a spot, multiply the choices” move is the multiplication rule, and it is behind everything on this page.
Permutations and n!#
A permutation of n objects is an ordering of all of them, each used exactly once. The set of all permutations of n objects is written Sn.
By the multiplication rule there are n · (n − 1) · … · 2 · 1 of them. That product is written n! and read “n factorial”.
|Sn| = n! So 3! = 6, 4! = 24, 5! = 120.
A permutation is also a bijection from a set to itself: position 1 goes to some letter, position 2 to another, and no letter is used twice. That is the link to functions.
Why n! is right: the induction from the lecture#
Here is how to build every permutation of n + 1 letters from the permutations of n letters, with nothing missed and nothing repeated.
Take a permutation of A, B, C, for example ABC. It has 4 gaps: before A, between A and B, between B and C, after C. Drop the new letter D into each gap:
DABC, ADBC, ABDC, ABCD.
Do this for all 6 permutations of ABC, and you get 6 · 4 = 24 words.
- Within one group the words differ, because D sits in a different position in each.
- Across two groups the words differ too. Delete D from both and you get two different permutations of ABC.
So |S4| = 4 · |S3|, and in general |Sn+1| = (n + 1) · |Sn|. Together with |S1| = 1, induction gives |Sn| = n!.
“2 · 3” means 2 rows of 3 objects. “3 · 2” means 3 rows of 2. Turning the rectangle 90° is a bijection between them, which is why 2 · 3 = 3 · 2. The 24 words above really are 6 rows of 4.
Arrangements: ordering only some of the letters#
Now use only some of the letters. From the alphabet {A, B, C, D}, how many 2-letter words with two different letters are there? Order matters, so AB and BA are different words.
| AB | AC | AD |
| BA | BC | BD |
| CA | CB | CD |
| DA | DB | DC |
There are 4 choices for the first letter and 3 for the second: 4 · 3 = 12. This is an arrangement, also called a partial permutation, written P(4, 2).
In general, choosing n letters in order from an alphabet of m:
P(m, n) = m · (m − 1) · (m − 2) · … · (m − n + 1)
That product has exactly n factors: one per position. Stop after n of them. For example P(7, 3) = 7 · 6 · 5 = 210.
Two useful facts. P(n, n) = n!, since using all n letters is a full permutation. And P(m, n) = m!/(m − n)!, since the factors below m − n + 1 cancel.
Adding a letter to the alphabet#
The lecture’s induction on m compares P(m + 1, n) with P(m, n). Write them side by side for m = 7, n = 3:
P(7, 3) = 7 · 6 · 5 = 210 and P(8, 3) = 8 · 7 · 6 = 336.
The new one gains a factor 8 at the top and loses the factor 5 at the bottom. In general:
P(m + 1, n) = (m + 1)/(m − n + 1) · P(m, n).
Check: 210 · 8/5 = 336. The worked case in the lecture, going from 4 letters to 5 with n = 4, is the easy version: the bottom factor there is 1, so P(5, 4) = 5 · 4! = 120.
Counting functions#
Arrangements also count functions. How many functions go from {a, b, c} to {1, 2, 3, 4}?
- Any function: each of the 3 inputs picks any of the 4 outputs. 4 · 4 · 4 = 43 = 64.
- Injective (one-to-one) functions: outputs may not repeat. 4 · 3 · 2 = P(4, 3) = 24.
The difference between those two numbers is the difference between “repeats allowed” (powers) and “no repeats” (arrangements).
How fast n! grows#
Factorials outrun every exponential eventually, because each new factor keeps getting bigger while the base of an exponential stays fixed.
| n | 2n | 3n | n! |
|---|---|---|---|
| 1 | 2 | 3 | 1 |
| 3 | 8 | 27 | 6 |
| 5 | 32 | 243 | 120 |
| 7 | 128 | 2,187 | 5,040 |
| 10 | 1,024 | 59,049 | 3,628,800 |
At n = 10, n! is already about 60 times 310. This is why a computer cannot simply try every ordering of a few dozen objects.
Fill the positions one at a time and multiply the choices: all n positions gives n!, and only n positions out of m letters gives P(m, n), which has exactly n factors.
Where this goes wrong#
- Too many factors. P(7, 3) is 7 · 6 · 5. Writing 7 · 6 · 5 · 4 counts 4-letter words.
- Using mn when repeats are banned. mn allows AA. Arrangements do not.
- Dividing by n! when order matters. m!/(n!(m − n)!) counts unordered choices, the subsets of size n. That is a different question.
- Writing m!/n! for P(m, n). The denominator is (m − n)!. The two agree by accident when m = 2n, which hides the mistake in small examples like P(4, 2).
Test yourself in the free Kestrel Exams app
Topic-selectable Discrete Math practice — offline, no ads, no account.
Practice permutations and arrangements →Frequently asked questions#
What is the formula for permutations?
The number of ways to order n distinct objects is n! = n · (n − 1) ⋯ 2 · 1. For ordered choices of n objects from m, the number is P(m, n) = m(m − 1)⋯(m − n + 1), which has n factors and equals m!/(m − n)!.
What is the difference between a permutation and an arrangement?
A permutation orders all of the objects. An arrangement (partial permutation) orders only some of them, n chosen from m. So P(n, n) = n! is the permutation case.
Why does n! count permutations?
There are n choices for the first position, n − 1 for the second, and so on down to 1. The lecture proves it by induction: inserting a new letter into each of the n + 1 gaps of every permutation of n letters produces every permutation of n + 1 letters exactly once.
How many one-to-one functions are there from a 3-element set to a 4-element set?
24. The first input has 4 possible outputs, the second has 3 left, the third has 2: 4 · 3 · 2 = P(4, 3) = 24. Without the one-to-one condition there are 4³ = 64 functions.
Something here not clear? A topic you wish we covered? Tell us. We read every message, and a request is the fastest way to get a guide written — several of these exist because somebody asked.