Q. 2.17 - A First Course in Probability

Question

Consider the matching problem, Example$5m$, and define it 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 = (N - 1)(A_{N-1} + A_{N-2})$. This formula, along with the boundary conditions$A_1 = 0, A_2 = 1$, can then be solved for$A_N$, and the desired probability of no matches would be $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 do 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.

Step-by-Step Solution

Answer

$A_N=(N-1)\left(A_{N-1}+A_{N-2}\right)$

Step 1 Given Information.

Consider the matching problem, Example$5m$, and define $A_N$it to be the number of ways in which the$N$ men can select their hats so that no man selects his own.

Step 2 Explanation.

There are $K$men, and each man has their own hat, after the experiment, the hats are permuted among men, so each man has a different hat.

$A_N$- the number of ways in which the experiment ends so that no men have their hats.

Now let's try to express $A_N$recursively using the hint.

Count the number of ways in which none of $N$the men selects the right hat.

Since the ordering of man-hat pairs is not important, select a man, and he can be paired with one of the $(N-1)$hats.

Let's say he chose the hat of the $i$-th man.

For each pairing of the selected man and a hat, there remains $N-1$a man and $N-1$hat.

If the $i$-th man selects the hat of the first man, the remaining $N-2$people can choose from their$N-2$ hats, and they can choose hats that are not theirs in $A_{n-2}$ways.

And if $i$a -th man doesn't select the hat of the first man, each of the $N-1$men cant choose one of the $N-1$hats, the number of such choices is$A_{n-1}$.

So the remaining people can choose hats in $A_{N-1}+A_{N-2}$ways if none of them selects their own hat.

By the basic principle of counting

$A_N=(N-1)\left(A_{N-1}+A_{N-2}\right)$