Probability No One Gets Their Own Hat
$n$ men attend a formal party where they check their distinct hats into a closet at the entrance. At the end of the night the lights go out, and each man grabs a hat uniformly at random (without replacement, so the result is a random permutation of all $n$ hats).
Let $p(n)$ be the probability that *none* of the $n$ men ends up with his own hat.
- Derive a closed-form expression for $p(n)$.
- Evaluate $p(5)$.
Hints
- Think about the complementary event: instead of counting arrangements where nobody matches, count those where at least one person does. What classical counting tool handles unions of overlapping events?
- Use inclusion-exclusion. The key simplification comes from exchangeability -- the probability that any specific set of $k$ people all get their hats back is $\frac{(n-k)!}{n!}$, which collapses $\binom{n}{k}$ identical terms into $\frac{1}{k!}$.
- After inclusion-exclusion, you should arrive at $p(n) = \sum_{k=0}^{n} \frac{(-1)^k}{k!}$. Recognize this as the partial sum of the Taylor series for $e^{-1}$, and plug in $n = 5$ to get the final answer.
Worked Solution
How to Think About It: This is the classic derangement problem -- counting permutations with no fixed points. The first instinct is to think about it person-by-person, but the selections are coupled (if person 1 grabs person 2's hat, person 2 can no longer get it), so direct counting is messy. The clean move is inclusion-exclusion on the complementary events: instead of counting arrangements where *nobody* matches, count those where *at least one* person matches and subtract from 1.
A useful gut check before any algebra: the probability that a single person matches is $1/n$. There are $n$ people, so by linearity the expected number of matches is exactly 1, regardless of $n$. That suggests the probability of zero matches should stabilize quickly -- and it does, converging to $1/e \approx 0.368$ almost immediately.
Quick Estimate: For $n = 5$, the answer is close to $1/e \approx 0.3679$. Since the derangement formula is the partial sum of the Taylor series for $e^{-1}$, the error from truncation at $n = 5$ is at most $1/6! \approx 0.0014$. So we expect something very close to $0.367$. In fact $11/30 \approx 0.3667$, which is spot on.
Approach: Define the "match" events and apply inclusion-exclusion, exploiting exchangeability to collapse the sum.
Formal Solution:
Let $H_i$ be the event that person $i$ gets their own hat back. We want
$$p(n) = P\!\left(\bigcap_{i=1}^{n} H_i^c\right) = 1 - P\!\left(\bigcup_{i=1}^{n} H_i\right).$$
By inclusion-exclusion,
$$P\!\left(\bigcup_{i=1}^{n} H_i\right) = \sum_{k=1}^{n} (-1)^{k+1} \sum_{|S|=k} P\!\left(\bigcap_{i \in S} H_i\right).$$
The key simplification: by exchangeability, $P\!\left(\bigcap_{i \in S} H_i\right)$ depends only on $|S| = k$, not on which $k$ people are in $S$. If $k$ specific people must each get their own hat, the remaining $n - k$ hats are permuted freely among the remaining $n - k$ people, giving
$$P\!\left(\bigcap_{i \in S} H_i\right) = \frac{(n-k)!}{n!}.$$
There are $\binom{n}{k}$ choices of $S$, and $\binom{n}{k} \cdot \frac{(n-k)!}{n!} = \frac{1}{k!}$. So
$$P\!\left(\bigcup_{i=1}^{n} H_i\right) = \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!}.$$
Therefore,
$$p(n) = 1 - \sum_{k=1}^{n} \frac{(-1)^{k+1}}{k!} = \sum_{k=0}^{n} \frac{(-1)^k}{k!}.$$
This is exactly the first $n+1$ terms of the Taylor expansion of $e^{-1}$, which is why $p(n) \to 1/e$ as $n \to \infty$.
For $n = 5$:
$$p(5) = 1 - 1 + \frac{1}{2} - \frac{1}{6} + \frac{1}{24} - \frac{1}{120} = \frac{60 - 20 + 5 - 1}{120} = \frac{44}{120} = \frac{11}{30}.$$
Sanity checks: - $p(1) = 1 - 1 = 0$. Correct -- one person always gets their own hat. - $p(2) = 1 - 1 + 1/2 = 1/2$. Correct -- two people swap with probability $1/2$. - $p(5) = 11/30 \approx 0.3667$, close to $1/e \approx 0.3679$. Checks out.
Answer: $p(n) = \displaystyle\sum_{k=0}^{n} \frac{(-1)^k}{k!}$, and $p(5) = \dfrac{11}{30}$.
Intuition
This is the derangement problem, one of the oldest and most elegant results in combinatorics. The remarkable fact is that the probability of a complete mismatch barely depends on $n$ at all -- it converges to $1/e$ so fast that by $n = 5$ you are already within $0.1\%$ of the limit. The reason is that inclusion-exclusion produces the partial sums of the exponential series, and the exponential series converges extremely rapidly thanks to the $k!$ in the denominator.
In quant interviews, derangements show up as a vehicle for testing whether you can wield inclusion-exclusion cleanly and whether you recognize the connection to the exponential function. The broader lesson is that when you have $n$ overlapping "bad" events that are exchangeable, inclusion-exclusion often telescopes into something beautiful. Practically, the $1/e$ rule of thumb is useful in any matching or assignment context -- roughly 37% of the time, a random assignment has zero correct matches.