Probability of matching events 
Possible Duplicate:
Number of permutations where n ≠ position n 

I have the following exercise:
Suppose that four guests check their hats when they arrive at a restaurant, and that these hats are returned to them in a random order when they leave. 
Determine the probability that no guest will receive the proper hat.
I'm not sure how to find out that no guest will receive the proper hat...
Can someone help me with an intuitive explanation from which I could start out?
 A: 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.
A: 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$.
