# n people & n hats: probability that at least 1 person has his own hat

Suppose n people take n hats at random. What is the probability that
at least 1 person has his own hat?

The proposed solution uses inclusion-exclusion principle and gives the answer:

$$\sum^{n}_{r=1} (-1)^{r-1} \frac{1}{r!}$$

But I think there is simpler solution: let’s calculate the complement, i.e. no one gets his own hat.

Total number of ways of distribution hats = number of permutations of hats, i.e. $n!$ Number of ways when no one gets his own hat is calculated as follows: fix a person, he can choose among n-1 hats, then, fix another person, he has n-2 hats at his disposal, and so on. This leads to $(n-1)!$

Therefore, my answer is $1 – \frac{(n-1)!}{n!} = 1 – \frac{1}{n}$ which is wrong. My question is where did I make a mistake?

#### Solutions Collecting From Web of "n people & n hats: probability that at least 1 person has his own hat"

… fix a person, he can choose among $n-1$ hats, then, fix another person, he has $n-2$ hats at his disposal

If the first person takes another person’s hat, then another person has $n-1$ different hats at his disposal.

The number you are trying to get is called the number of derangements and is also (most easily, I believe) computed by inclusion-exclusion principle.

The mistake is that the number of possibilities for the second person (and subsequent ones) to pick a hat besides his depends on what’s happened before. For example, if person number 1 picked hat number 2, there will be $n-1$ possibilities. Otherwise, $n-2$. I’m not sure how easy it is to give a proof along these lines that keeps track of these possibilities.

Adding to one other responder’s solution and explaining how to use derrangement in this kind of problem, I have taken n to be equal to 4 to lay down the foundation:

The total number of ways 4 people will receive 4 hats $= 4!$

The total number of ways that none of the person will get his own hat often defined as the derrangement notated by $(!4) = 9$ (Check Wolfram or Wiki).

Thus the probability that none of the 4 people will get their hats back $$= \frac{!4}{4!} = \frac{9}{24}$$

Thus the probability that atleast one person will get his hat back $$= 1 – \frac{9}{24} = \frac{15}{24}$$

If you evaluate the series in your answer for the problem, you will

$$= 1 – \frac{1}{2!}+\frac{1}{3!}-\frac{1}{4!} = \frac{15}{24}$$

Thanks
Satish