Consider the matching problem Example 5m and define An to be

Consider the matching problem, Example 5m, and define An to be the number of ways in which the N men can select their hats so that selects his own. Argue that A_N = (N - 1)(A_N - 1 + A_N - 2) This formula, along with the boundary conditions A1 = 0, A2 = 1, can then be solved for AN, and the desired probability of no matches would be AN/N!

Solution

after the first man selects a hat that is not his own there remain N-1 men toselect 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 .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