A hat-check girl receives \(n\) hats from \(n\) patrons, but forgets which hats belong to whom. So, she randomly disperses the hats back to the patrons.
What is the probability \(p_n\) that nobody has their hat returned to them?
A derangement is a permutation of a set such that no element remains in its original position. The number of derangements for a set of size \(n\) is denoted as \(!n\).
For this problem, each derangement represents a dispersal of hats such that nobody receives their hat back. Thus, the proportion of derangements among all possible permutations of the \(n\) hats is the probability that nobody has their hat returned to them:
\[p_n = \frac{!n}{n!}\]
For reasonably large \(n\) (\(n \geq 8\)), \(!n\) is very closely approximated by \(!n = \frac{n!}{e}\). Applying this approximation gives the following:
\[p_n = \frac{!n}{n!} = \frac{\frac{n!}{e}}{n!} = \frac{1}{e}\]