Permutations
Counting Ordered Arrangements — Where Every Position Matters
1. What Is a Permutation?
A permutation is an ordered arrangement of objects. The crucial idea is that order matters.
Key Idea: If you rearrange the same objects into a different sequence, you get a different permutation.
Consider the set $\{A, B, C\}$. How many ways can we line up all three letters?
| # | Arrangement |
|---|---|
| 1 | A B C |
| 2 | A C B |
| 3 | B A C |
| 4 | B C A |
| 5 | C A B |
| 6 | C B A |
There are 6 permutations. Notice that ABC and BAC contain the same letters but are counted separately because the order is different.
Fun Fact: A "combination lock" should really be called a permutation lock — the order you enter the numbers absolutely matters! Entering 3-7-1 is not the same as 1-3-7.
2. The Factorial Function
The factorial of a non-negative integer $n$, written $n!$, is the product of all positive integers from $1$ up to $n$:
$$ n! = n \times (n-1) \times (n-2) \times \cdots \times 2 \times 1 $$
It counts the number of ways to arrange $n$ distinct objects in a line.
Common Factorial Values
| $n$ | $n!$ | Calculation |
|---|---|---|
| 0 | 1 | (by definition) |
| 1 | 1 | $1$ |
| 2 | 2 | $2 \times 1$ |
| 3 | 6 | $3 \times 2 \times 1$ |
| 4 | 24 | $4 \times 3 \times 2 \times 1$ |
| 5 | 120 | $5 \times 4 \times 3 \times 2 \times 1$ |
| 6 | 720 | $6!$ |
| 10 | 3,628,800 | $10!$ |
| 20 | 2,432,902,008,176,640,000 | $20!$ — over 2 quadrillion! |
Why is $0! = 1$? This is not arbitrary — there is exactly one way to arrange zero objects: do nothing. It also keeps formulas like $P(n,0) = \frac{n!}{n!} = 1$ consistent.
⚠️ Factorials grow incredibly fast! $20!$ already exceeds 2 quadrillion. This explosive growth is why even modest counting problems can produce enormous numbers.