Probability of matching events [duplicate]

Solution 1:

Hint: If you want the practical answer just list the different patterns ($4!=24$) and see which match or not, perhaps starting

ABCD - match 4
ABDC - match 2

etc. and ending

DCBA - no matches

and then count the results.

Solution 2:

This is called the derangement problem.

Let $A_g$ denote the event that guest $g$ is given back the proper hat. One asks for the probability of the intersection $B$ of every $(A_g)^c$, hence $1-\mathrm P(B)$ is the probability of the union of the $A_g$. By the exclusion-inclusion principle, $$ 1-\mathrm P(B)=\sum_{k\geqslant1}(-1)^{k-1}\sum_{|G|=k}\mathrm P(A_G), $$ where for every subset $G$ of the set of guests, $A_G$ is the intersection of every $A_g$ such that $g$ is in $G$.

For every $G$ with $|G|=k$, there are $(n-k)!$ ways to give back their hats to the $(n-k)$ guests not in $G$ and one way to give back their hats to the $k$ guests in $G$ hence $\mathrm P(A_G)=(n-k)!/n!$. There are ${n\choose k}$ such subsets $G$ hence $$ 1-\mathrm P(B)=\sum_{k=1}^n(-1)^{k-1}{n\choose k}\frac{(n-k)!}{n!}=\sum_{k=1}^n\frac{(-1)^{k-1}}{k!}. $$ Finally, the probability that no guest receives the proper hat is $$ \mathrm P(B)=\sum_{k=0}^n\frac{(-1)^{k}}{k!}. $$ Note that $P(B)\to\mathrm e^{-1}$ when $n\to\infty$.