Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question

marked as duplicate by Henry, Mike Spivey, Zev Chonoles Oct 21 '11 at 18:30

This question has been asked before and already has an answer. If those answers do not fully address your question, please ask a new question.

2  
With only four people you can just list and count the derangements and divide by $4!$, or twenty-four. But more generally, this would be a duplicate of math.stackexchange.com/questions/14666/… or math.stackexchange.com/questions/17320/… –  anon Oct 16 '11 at 10:16
1  
Since there are in total only 24 possible orderings of the hats, the number of combinations that satisfy the requirement will be smaller. Therefore, it's not much work to try to write them down explicitly. To do it systematically, maybe writing down a decision tree helps? –  Raskolnikov Oct 16 '11 at 10:22

2 Answers 2

up vote 1 down vote accepted

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$.

share|improve this answer

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.

share|improve this answer

Not the answer you're looking for? Browse other questions tagged or ask your own question.