Chapter 2, Problem 2.17TE

Consider the matching problem. Example 5m, and define $A_N$ to be the number of ways in which the N men can select their hats so that no man selects his own. Argue that $A_N=\left(N-1\right)\left(A_{N-1}+A_{N-2}\right)$

This formula, along with the boundary conditions A₁ = 0, A₂ = 1, can then be solved for AN, and the desired probability of no matches would be $\frac{A_N}{N}$ !

Hint: After the first man selects a hat that is not his own, there remain N - 1 men to select among a set of N - 1 hats that does not contain the hat of one of these men. Thus, there is one extra man and one extra hat. Argue that we can get no matches either with the extra man selecting the extra hat or with the extra man not selecting the extra hat.