Probability exactly one person gets their own hat

Question

n hats are returned to their n owners in a uniformly random permutation. What is the probability that exactly one person receives their own hat? What does it converge to as n 	o \infty?

Accepted Answer

Count the permutations with exactly one fixed point. Pick the lucky person in \binom{n}{1} = n ways; the other n - 1 hats must be a derangement of their owners so that nobody else matches. Writing Dm for the number of derangements of m items, P(	ext{exactly one match}) = \frac{n \cdot D{n-1}}{n!} = \frac{D{n-1}}{(n-1)!}. Since \dfrac{D{m}}{m!} = \sum{k=0}^{m} \dfrac{(-1)^k}{k!}, we get P(	ext{exactly one match}) = \sum{k=0}^{n-1} \frac{(-1)^k}{k!} \ \xrightarrow{n	o\infty}\ \frac{1}{e} \approx 0.3679. For a concrete check, n = 4: D3 = 2, so P = \dfrac{4 \cdot 2}{24} = \dfrac{8}{24} = \dfra…

Probability exactly one person gets their own hat

Your answer

More Probability questions