Mix up $n$ letters and $n$ envelopes at random: how likely is it that no letter ends up in its own envelope? Counting the arrangements with nothing in its place takes inclusion–exclusion over all the ways things can go right, together with permutations of what remains.
🔑 Key idea
A derangement of $n$ items is an arrangement with no item in its original place. Their number is $$D_{n} = n!\left(1 - \frac{1}{1!} + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^{n}}{n!}\right).$$ The first values are $D_{1} = 0$, $D_{2} = 1$, $D_{3} = 2$, $D_{4} = 9$, $D_{5} = 44$, $D_{6} = 265$, and $D_{n}/n!$ approaches $1/e \approx 0.368$.
💡 Why it works
Let $A_{i}$ be the arrangements that leave item $i$ in place. We want the arrangements in none of the $A_{i}$: all $n!$ minus $|A_{1} \cup \cdots \cup A_{n}|$. If $k$ particular items are fixed, the other $n - k$ can be arranged freely: $(n - k)!$ ways. There are $\binom{n}{k}$ ways to choose which $k$ are fixed. Inclusion–exclusion alternates signs: $$D_{n} = \sum_{k=0}^{n} (-1)^{k}\binom{n}{k}(n - k)! = \sum_{k=0}^{n} (-1)^{k}\frac{n!}{k!}.$$ The bracket in the key is the start of the series for $e^{-1}$, which is why the fraction settles near $0.368$ so quickly.
Worked examples
✏️ Worked example: Four letters
Find $D_{4}$.
- $D_{4} = 4! - \binom{4}{1}3! + \binom{4}{2}2! - \binom{4}{3}1! + \binom{4}{4}0!$.
- $= 24 - 24 + 12 - 4 + 1 = 9$.
- Listing them confirms it: 2143, 2341, 2413, 3142, 3412, 3421, 4123, 4312, 4321.
Answer: $9$
✏️ Worked example: The hat check
Five guests' hats are handed back at random. What is the probability that nobody gets their own hat?
- All handouts: $5! = 120$.
- $D_{5} = 120 - 120 + 60 - 20 + 5 - 1 = 44$.
- Probability $\frac{44}{120} = \frac{11}{30} \approx 0.367$, already close to $\frac{1}{e}$.
Answer: $\frac{11}{30}$
Derangements next to all arrangements.| $n$ | $n!$ | $D_{n}$ | $D_{n}/n!$ |
|---|
| $3$ | $6$ | $2$ | $0.3333$ |
| $4$ | $24$ | $9$ | $0.3750$ |
| $5$ | $120$ | $44$ | $0.3667$ |
| $6$ | $720$ | $265$ | $0.3681$ |
| $7$ | $5{,}040$ | $1{,}854$ | $0.3679$ |
The fraction settles almost at once: from $n = 6$ on it agrees with $\frac{1}{e} = 0.36787\ldots$ to three decimal places. So whether $10$ or $1{,}000$ people swap gifts at random, the chance that nobody draws their own name is about $37\%$. There is also a recurrence, $D_{n} = (n - 1)(D_{n-1} + D_{n-2})$, which lets you build the list one step at a time.
✏️ Worked example: Exactly two in place
How many arrangements of $5$ items leave exactly $2$ items in their places?
- Choose the $2$ that stay: $\binom{5}{2} = 10$.
- The other $3$ must all move: $D_{3} = 2$.
- $10 \cdot 2 = 20$.
Answer: $20$
⚠️ Common mistake
Subtracting the single fixed points and stopping. "All arrangements minus those with some item fixed" done as $4! - 4 \cdot 3! = 0$ cannot be right; there are derangements of $4$ items. An arrangement fixing two items was subtracted twice, once for each. Check: the inclusion–exclusion sum must alternate all the way to the term for all $n$ items, and the answer can be checked against the recurrence $D_{n} = (n - 1)(D_{n-1} + D_{n-2})$.