1
A derangement has no fixed point
σ(i) ≠ i for every i. The hat-check problem: nobody gets their own hat.
Lesson · Combinatorics and Counting · Corrections
Derangements
A derangement moves every element. Inclusion and exclusion counts them, and the proportion of permutations that are derangements converges to 1/e almost immediately — it is already accurate at n = 7.
Dₙ = n! · Σ_{k=0}^{n} (−1)^k / k!
Dₙ / n! → 1/e ≈ 0.3679 and fast
D₁=0 D₂=1 D₃=2 D₄=9 D₅=44 D₆=265
Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂) a recurrence too
The canonical application
Core ideas
What this lesson establishes
Derangements are the standard worked example of inclusion and exclusion, and their limit is genuinely surprising.
2
Inclusion and exclusion counts them
Let Aᵢ be the permutations fixing i. Then |Aᵢ| = (n−1)! and the intersections are similarly clean, so the alternating sum closes.
3
The proportion converges immediately
Dₙ/n! is within 10⁻⁴ of 1/e by n = 7. The chance that nobody gets their own hat is essentially the same for 10 people and for 10 million.
The material
Counting derangements
The derivation, the recurrence, and the limit.
Definition · Derangement
A derangement of {1, …, n} is a permutation σ with σ(i) ≠ i for every i. Dₙ denotes the number of them.
Theorem · The derangement formula
Dₙ = n! Σ_{k=0}^{n} (−1)^k / k! = n! (1 − 1/1! + 1/2! − 1/3! + ⋯ + (−1)ⁿ/n!).
Let Aᵢ be the set of permutations fixing i. A permutation is a derangement exactly when it lies in none of the Aᵢ, so Dₙ = n! − |A₁ ∪ ⋯ ∪ A_n|.
Fixing a specified set of k elements leaves the other n − k free, so each k-fold intersection has (n−k)! members, and there are C(n,k) such intersections.
By inclusion and exclusion, Dₙ = Σ_{k=0}^{n} (−1)^k C(n,k)(n−k)! = Σ_{k=0}^{n} (−1)^k n!/k!, which is the stated formula.
□
n 1 2 3 4 5 6 7 8
n! 1 2 6 24 120 720 5040 40320
Dₙ 0 1 2 9 44 265 1854 14833
Dₙ/n! 0 .500 .333 .375 .3667 .36806 .367857 .3678819
1/e ≈ 0.3678794412
The convergence is startlingly quick because the series for 1/e alternates with rapidly shrinking terms: the error after n terms is below 1/(n+1)!. By n = 7 that is under 1/40320.
Theorem · Rounding formula
Dₙ is the nearest integer to n!/e for every n ≥ 1, which follows from the same error bound.
Theorem · A recurrence
Dₙ = (n−1)(Dₙ₋₁ + Dₙ₋₂) for n ≥ 3, with D₁ = 0 and D₂ = 1.
In a derangement, element 1 goes to some position j ≠ 1, and there are n − 1 choices of j. Split on what happens to j:
If j goes to position 1, the remaining n − 2 elements form a derangement among themselves: Dₙ₋₂ ways.
If j does not go to position 1, then treating "position 1" as the forbidden position for j makes the remaining n − 1 elements a derangement of n − 1 items: Dₙ₋₁ ways.
So Dₙ = (n−1)(Dₙ₋₂ + Dₙ₋₁).
□
Two derivations of the same numbers, by different techniques. The recurrence is a case split of the kind “Recurrence Relations” in Induction and Recursion taught; the formula came from inclusion and exclusion. Agreement between them is a genuine check, and both are worth having.
Example · The hat-check problem
n people check hats and receive them back at random. The probability nobody gets their own is Dₙ/n!, which for n ≥ 7 is 0.3679 to four places whatever n is — at n = 5 it is still 0.3667 and at 6 it is 0.3681. Discrete Probability makes the division into a probability statement.
Interactive
Derangements
Three routes to one number
Method
Using derangements
Recognise the "nothing in its own place" shape.
1
Check every element has exactly one forbidden position
That is what makes it a derangement. More complicated forbidden patterns need the permanent of a matrix and are outside this course.
2
Use the formula or the recurrence
The recurrence is faster by hand for small n; the formula is what generalises.
3
For a partial condition, combine with combinations
"Exactly k fixed points" is C(n,k)·D_{n−k}: choose which stay, derange the rest.
4
Check against n!/e
Dₙ is the nearest integer to n!/e. It is a one-line verification of an answer computed another way.
Derangements
Score 0 / 0Choose the answer you can justify.
Exactly two people get their own hat
Out of six people, how many outcomes fix exactly two?
Choose WHICH two get their own hat: C(6,2) = 15
Derange the other four so none is fixed: D₄ = 9
15 × 9 = 135 outcomes
Total outcomes: 6! = 720, so the proportion is 135/720 = 0.1875
Check by summing over all k:
Σ_k C(6,k)·D_{6−k}
= 265 + 6·44 + 15·9 + 20·2 + 15·1 + 6·0 + 1·1
= 265 + 264 + 135 + 40 + 15 + 0 + 1 = 720 = 6! ✓
The final check is the useful one: every permutation has exactly one number of fixed points, so summing over k must recover n!. D₀ = 1 — the empty permutation deranges vacuously — is what makes the last term come out right.
Common mistakes
1
Forgetting D₀ = 1The empty permutation has no fixed points, so it is a derangement. This convention is what makes Σ_k C(n,k)D_{n−k} = n! come out exactly.
2
Applying derangements to unequal forbidden setsDerangements assume each element has exactly one forbidden position. General forbidden-position problems are much harder.
3
Expecting the proportion to vary with nIt stabilises immediately. The chance nobody gets their own hat is the same for 8 people as for 8000, to four decimal places.
Check your understanding
✓
Finish when you can count "exactly k fixed points" unaided.
Compute the number of permutations of 7 elements with exactly three fixed points, then verify that summing your formula over all k from 0 to 7 gives 7! = 5040. The check is what confirms the setup.
Note: e appearing in a purely combinatorial count is not a coincidence: the alternating sum in the derangement formula is a truncation of the Taylor series for e⁻¹, and the truncation error is smaller than the gap between consecutive integers.