Nobody gets their own hat
Five people leave their hats in a cloakroom and later each receives one of the five hats, uniformly at random (all assignments are equally likely).
What is the probability that nobody receives their own hat?
Fractions, decimals with at least 3 significant digits, and expressions such as sqrt(2)/2, e^-1 or pi/4.
Use inclusion–exclusion on the events .
If given people all get their own hats, the other hats can be arranged in ways.
h
s Shown after a correct answer. Revealing it first marks the problem as seen, not solved.
Idea. “Nobody matches” is the complement of a union of events, and the intersections of those events are easy to count. Inclusion–exclusion does the rest.
Step 1: intersections. For any set of people, the probability that all of them get their own hats is . There are such sets, so the -th term of inclusion–exclusion is
Step 2: inclusion–exclusion.
So of the assignments give nobody their own hat, about .
In general. With people the probability is , which converges to very fast: from on it is already within . The expected number of people who get their own hat is exactly for every , by linearity.