Derangements and 1/e
Tonight's idea
\(n\) people check their hats and get them back in a random order, each of the \(n!\) orders equally likely. A derangement is an order in which nobody gets their own hat. Call the number of them \(D(n)\).
Count the opposite. Orders where person \(i\) does get their own hat number \((n-1)!\), since the other hats are free. Fix \(k\) chosen people and \((n-k)!\) orders remain, with \(\binom nk\) ways to choose them. Inclusion–exclusion (grade 6, b26) adds the singles, subtracts the pairs, adds the triples:
\[D(n) = n! - \binom n1 (n-1)! + \binom n2 (n-2)! - \cdots = n! \sum_{k=0}^{n} \frac{(-1)^k}{k!},\]
using \(\binom nk (n-k)! = n!/k!\). So the probability of a derangement is
\[\frac{D(n)}{n!} = 1 - 1 + \frac{1}{2!} - \frac{1}{3!} + \cdots + \frac{(-1)^n}{n!},\]
the series for \(e^x\) at \(x = -1\) (sheet a12) stopped at \(k = n\). So \(D(n)/n! \to 1/e \approx 0.3679\). An alternating series with shrinking terms misses its limit by less than the first omitted term, \(1/(n+1)!\). Times \(n!\), that is under \(1/(n+1)\), so \(D(n)\) is \(n!/e\) rounded to the nearest integer.
A recurrence avoids the sum. Person 1 receives hat \(j\): \(n - 1\) choices. Either person \(j\) receives hat 1 (a swap; the other \(n - 2\) must be deranged, \(D(n-2)\) ways) or not (then call hat 1 "\(j\)'s own"; \(n - 1\) people and hats must be deranged, \(D(n-1)\) ways).
\(D(n) = (n - 1)\big(D(n-1) + D(n-2)\big)\), with \(D(1) = 0\), \(D(2) = 1\).
Watch one: four hats
There are \(4! = 24\) orders. Orders with at least one own hat: \(4 \cdot 3! - 6 \cdot 2! + 4 \cdot 1! - 1 \cdot 0! = 24 - 12 + 4 - 1 = 15\), so \(D(4) = 9\). Check: \(24/e = 8.83\), which rounds to 9. Recurrence: \(3 \,(D(3) + D(2)) = 3 \,(2 + 1) = 9\). The nine are three double swaps, such as \(1 \leftrightarrow 2\) with \(3 \leftrightarrow 4\), and six 4-cycles. The probability is \(9/24 = 0.375\), already near \(0.368\). The recurrence continues:
\[D(1), \dots, D(8) = 0,\ 1,\ 2,\ 9,\ 44,\ 265,\ 1854,\ 14833.\]
Your turn
- Compute \(D(5)\) three ways: by inclusion–exclusion, by the recurrence, and as the nearest integer to \(120/e\).
- (a) Four people: what is the probability that exactly one gets their own hat? (b) Five people: exactly two?
- From the sum formula, prove the shorter recurrence \(D(n) = n\,D(n-1) + (-1)^n\). Check it with \(D(4)\) and \(D(5)\).
- (a) Show that the probability exactly \(k\) of \(n\) people get their own hat is \(\dfrac{D(n-k)}{k!\,(n-k)!}\). (b) Show that the expected number of people who get their own hat is exactly 1, for every \(n\), without using (a).
Stretch: the limit law
Using 4(a), show that as \(n \to \infty\) the probability that exactly \(k\) people get their own hat tends to \(e^{-1}/k!\), and that these limits add up to 1. Which distribution is this?
Answers
- Inclusion–exclusion: \(120 - 5 \cdot 24 + 10 \cdot 6 - 10 \cdot 2 + 5 \cdot 1 - 1 = 44\). Recurrence: \(4\,(D(4) + D(3)) = 4\,(9 + 2) = 44\). And \(120/e = 44.15\), nearest integer 44.
- (a) Choose the lucky person (4 ways) and derange the other three (\(D(3) = 2\) ways): \(8\) orders, probability \(8/24 = 1/3\). (b) \(\binom52 D(3) = 10 \cdot 2 = 20\) orders, probability \(20/120 = 1/6\).
- Split off the last term of the sum: \(n! \sum_{k=0}^{n} \frac{(-1)^k}{k!} = n \cdot (n-1)! \sum_{k=0}^{n-1} \frac{(-1)^k}{k!} + n! \cdot \frac{(-1)^n}{n!} = n\,D(n-1) + (-1)^n\). Check: \(4 \cdot 2 + 1 = 9\) and \(5 \cdot 9 - 1 = 44\).
- (a) Choose the \(k\) who get their own hats, \(\binom nk\) ways, and derange the other \(n - k\), \(D(n-k)\) ways. Divide by \(n!\) and use \(\binom nk / n! = 1/(k!\,(n-k)!)\). (b) Each person's own hat is equally likely to be any of the \(n\) hats returned, so each gets their own with probability \(1/n\). Expectations add even when the events depend on each other, so the expected count is \(n \cdot \tfrac1n = 1\).
Stretch. By 4(a) the probability is \(\dfrac{1}{k!} \cdot \dfrac{D(n-k)}{(n-k)!}\), and the second factor tends to \(1/e\) as \(n \to \infty\) with \(k\) fixed. So the limit is \(e^{-1}/k!\). Summing over \(k\): \(e^{-1} \sum_{k \ge 0} 1/k! = e^{-1} \cdot e = 1\). This is the Poisson distribution with mean 1 (sheet b13), and its mean 1 matches 4(b).