Derangements
What You'll Learn
You'll learn how to count permutations where every single object ends up in a different position from where it started.
What Is a Derangement?
A derangement is a permutation of objects where no object appears in its original position. Think of it as the "complete chaos" arrangement—nothing stays where it belongs.
Example: If you have hats labeled 1, 2, 3 for three people (also labeled 1, 2, 3), a derangement ensures person 1 doesn't get hat 1, person 2 doesn't get hat 2, and person 3 doesn't get hat 3. For three items, the derangements are:
- (2, 3, 1): person 1 gets hat 2, person 2 gets hat 3, person 3 gets hat 1
- (3, 1, 2): person 1 gets hat 3, person 2 gets hat 1, person 3 gets hat 2
That's 2 derangements out of 3! = 6 total permutations.
The Derangement Formula
The number of derangements of n objects is denoted D(n) or !n, and can be calculated using:
D(n) = n! × (1 - 1/1! + 1/2! - 1/3! + 1/4! - ... + (-1)^n/n!)
Or equivalently, the recurrence relation:
- D(0) = 1 (by convention)
- D(1) = 0 (one object must stay in place)
- D(n) = (n - 1) × [D(n - 1) + D(n - 2)] for n ≥ 2
Quick values: D(2) = 1, D(3) = 2, D(4) = 9, D(5) = 44
Interestingly, D(n)/n! approaches 1/e ≈ 0.368 as n grows, meaning roughly 37% of all permutations are derangements!
Key Takeaway: A derangement is a permutation with no fixed points—computed via D(n) = n! × Σ((-1)^k/k!) or the recurrence D(n) = (n-1)[D(n-1) + D(n-2)].