On this page
Write four letters, address four envelopes, then put the letters in at random. In how many ways can every letter end up in the wrong envelope? That is the derangement question, a staple of permutations practice for JEE and olympiad maths. The method that answers it, inclusion-exclusion, also handles versions where some letters land correctly.
What is a derangement?
A derangement is a permutation of distinct objects in which none stays in its original position, as Wolfram MathWorld's entry on derangements defines it. For the items 1, 2, 3, only two of the six orders qualify: 2, 3, 1 and 3, 1, 2.
The number of derangements of n items is written !n and called the subfactorial. The sequence for n = 0, 1, 2, 3, … begins 1, 0, 1, 2, 9, 44, 265, 1854 (OEIS A000166).
MathWorld records that Pierre Rémond de Montmort posed it in 1708 and solved it in 1713, and that Nicholas Bernoulli solved it independently using inclusion-exclusion. OEIS notes that Leonhard Euler later proved both of the standard recurrences.
How do you count derangements with inclusion-exclusion?
Count the bad arrangements and subtract them. Let Aᵢ be the arrangements where item i is in its own place. The derangements are everything outside A₁ ∪ A₂ ∪ … ∪ Aₙ.
If you insist that k particular items stay put, the other n − k can go anywhere: (n − k)! arrangements.
There are C(n, k) ways to choose which k items those are.
Inclusion-exclusion alternates signs: subtract the single overlaps, add back the pairs, subtract the triples, and so on.
So !n = Σ (−1)ᵏ C(n, k)(n − k)! for k = 0 to n. Because C(n, k)(n − k)! = n!/k!, this tidies into the formula on MathWorld: !n = n!(1 − 1/1! + 1/2! − 1/3! + … + (−1)ⁿ/n!).
If the alternating signs feel shaky, practise them on three-set Venn problems with inclusion-exclusion first; the logic is the same with n sets.
To check answers, use the recurrence !n = (n − 1)(!(n − 1) + !(n − 2)) from OEIS A000166: !4 = 3 × (2 + 1) = 9 and !5 = 4 × (9 + 2) = 44.
Worked example: four letters, four envelopes
There are 4! = 24 ways to fill the envelopes. Apply the formula term by term:
Start with all arrangements: 24.
Subtract, for each letter, the arrangements with that letter correct: 4 × 3! = 24.
Add back pairs: C(4, 2) × 2! = 12.
Subtract triples: C(4, 3) × 1! = 4.
Add the case where all four are correct: 1.
So !4 = 24 − 24 + 12 − 4 + 1 = 9. The chance that every letter is wrong is 9/24 = 3/8, and the number of ways at least one letter is right is 24 − 9 = 15.
How many arrangements leave exactly k items fixed?
Choose which k items stay in place, then derange all the rest. The count is C(n, k) × !(n − k), the partial derangement or rencontres number described on MathWorld's partial derangement page.
Take five letters with exactly two in the right envelopes: C(5, 2) × !3 = 10 × 2 = 20. The full row for five letters, from zero to five correct, is 44, 45, 20, 10, 0, 1 (OEIS A008290). Those add up to 120 = 5!, so every arrangement is counted once.
Why does the probability settle near 1/e?
The bracket 1 − 1/1! + 1/2! − … is the start of the series for e⁻¹. MathWorld states that the probability a random permutation has no fixed point approaches 1/e ≈ 0.368, and that the approximation is already close at n = 4. OEIS gives the shortcut that, for n ≥ 1, !n is n!/e rounded to the nearest whole number: 120/e ≈ 44.1, which rounds to 44.
In everyday terms, if a large group of friends draws names for a gift exchange, the chance that nobody draws their own name is about 37%, whether there are 10 people or 100.
A checklist for derangement questions in exams
Read the condition. "No item in its own place" means !n.
"Exactly k in place" means C(n, k) × !(n − k).
"At least one in place" means n! − !n.
"At most k in place" means adding the exact cases from 0 to k.
Do not confuse "all wrong" with "not all right". The second is n! − 1.
Sanity check: confirm the cases add to n!, and compare !n with n!/e.
If you keep picking the wrong case, the Fermi Problem Library has worked problems with a step-by-step solver that explains the reasoning rather than printing an answer. If factorials or inclusion-exclusion are the real gap, the Fermi Concept Library gives each mathematics concept its own lesson and its place in the map.
For the wider habit of counting each case once, read our guide to stopping double counting in permutations and combinations.
