The puzzle
At a party, n guests hand in their hats. The hats get mixed up, and each guest is given back one hat at random, with every hat going to exactly one person. What is the chance that nobody receives their own hat?
Most people guess the answer should fall as the party gets bigger, since there are more chances for someone to be lucky. The surprise is that it does not. For any reasonably sized group the chance is about 37 percent, and the group size hardly matters.
The same structure appears whenever items are matched at random to positions: shuffled letters going into the wrong envelopes, a deck being compared card by card with its original order, or a secret-gift exchange where nobody should draw their own name.
Derangements: the counting term
A rearrangement of items in which no item stays in its original position is called a derangement. If D(n) is the number of derangements of n items, then the probability that nobody gets their own hat is D(n) ÷ n!, because n! counts all the equally likely ways to hand the hats back. This is the same factorial count used for any full ordering of n distinct things.
Counting small cases by hand
One guest. Their only hat is their own, so D(1) = 0.
Two guests, A and B. Of the 2 arrangements, one gives each their own hat and the other swaps them. Only the swap counts, so D(2) = 1, and the probability is 1/2.
Three guests, A, B, C. There are 3! = 6 arrangements. List the hat each guest receives, in order A, B, C:
- A B C: everyone correct, no
- A C B: A correct, no
- B A C: C correct, no
- C B A: B correct, no
- B C A: nobody correct, yes
- C A B: nobody correct, yes
So D(3) = 2, and the chance is 2/6, about 33.3 percent.
Four guests. There are 4! = 24 arrangements. A careful count (or the formulas below) gives D(4) = 9, so the probability is 9/24 = 0.375, or 37.5 percent.
A recursion that builds the counts
Counting the larger cases by listing becomes tiresome. There is a useful rule connecting each count to the two before it:
D(n) = (n − 1) × [D(n − 1) + D(n − 2)].
Check it on what we know. With D(1) = 0 and D(2) = 1, D(3) = 2 × (1 + 0) = 2, which matches the list above. Then:
- D(4) = 3 × (2 + 1) = 9
- D(5) = 4 × (9 + 2) = 44
- D(6) = 5 × (44 + 9) = 265
The rough reasoning behind the rule: look at what happens to guest 1’s hat. It must go to one of the other n − 1 guests, say guest j. Either guest j’s hat goes to guest 1 (a swap, after which the remaining n − 2 people must form a derangement), or it does not (and the remaining situation behaves like a derangement of n − 1 items). Counting both cases for each of the n − 1 choices of j gives the rule.
Now divide each count by n!:
| Guests | Derangements | Total arrangements | Chance nobody matches |
|---|---|---|---|
| 3 | 2 | 6 | 0.3333 |
| 4 | 9 | 24 | 0.3750 |
| 5 | 44 | 120 | 0.3667 |
| 6 | 265 | 720 | 0.3681 |
The last column wobbles slightly and then settles. It does not shrink as n grows.
Why about 37 percent
A direct formula comes from the inclusion-exclusion principle. Start with all n! arrangements, then subtract those in which a chosen guest gets their own hat, add back the ones where two chosen guests both do, and so on, alternating. This gives
D(n) = n! × (1 − 1/1! + 1/2! − 1/3! + … ± 1/n!).
So the probability that nobody matches is the partial sum
1 − 1 + 1/2 − 1/6 + 1/24 − …
Terms get very small quickly, since each is divided by a factorial. As n grows, the sum approaches the number e⁻¹ = 1/e, which is about 0.3679. That is the 37 percent figure (more precisely about 36.8 percent). By the time n reaches 6 or so, the actual probability agrees with 1/e to about three decimal places.
You can double-check the logic using a complement. The chance that at least one guest gets their own hat is therefore about 1 − 0.368 = 0.632, or about 63 percent. This follows the complement rule: counting “nobody matches” is often easier than counting “somebody matches” directly.
What this does and does not say
The result says that, for random matching, the chance of zero matches is close to 37 percent for any sizable group. It also says something about the average number of matches. The expected number of guests who get their own hat is 1, regardless of n. Each guest has a 1/n chance of getting the right hat, and n guests times 1/n gives 1. That is a pleasant use of expected value, and it does not contradict the 37 percent figure: sometimes there are zero matches, sometimes one, occasionally more, and the average comes out at one.
Derangements also matter when you shuffle a deck and compare it to a reference order. With 52 cards, the chance that no card lands in its original position is again about 0.368. Because all 52! orderings are equally likely under a fair shuffle, this is just the same sum evaluated for n = 52, which is indistinguishable from 1/e at normal precision.
This is a statement about random matchings. It is not a method for predicting anything in a game of chance, and each shuffle or deal is independent of earlier ones.