# Suppose that each of $n$ men at a party throws his hat into the center of the room...

Suppose that each of $$n$$ men at a party throws his hat into the center of the room. The hats are mixed up and then each man randomly selects a hat. What is the probability that at least one of the men selects his own hat?

• I typically try to post my attempted solutions to all of my math questions, but this one (and another I have posted just now) has me entirely stumped. Its an example from my notes that I just didn't get, so it is not a homework problem. I'll try to solve it, but based on what is in my notes (copied down from my professor), I entirely don't understand the process of solving it. Commented Oct 11, 2017 at 8:31
• I believe inclusion-exclusion is the way to go here.
– user418131
Commented Oct 11, 2017 at 8:34
• A permutation in which no man selects his own hat is a derangement. What you wish to calculate is the probability that a derangement does not occur. Commented Oct 11, 2017 at 10:06

It has to do with derangements: $n!-D(n)$.

First of all it's a uniform probability space therefore:

Let's define the event: $A_0$ = {no man selects his own hat}

Therefore we know that $B_0$ = {at least one man select his own hat} = $S_n-A_0$, where $S_N$ is the set of all permutations.

Using the Inclusion–exclusion principle we find that |$A_0$| = $D_n$ = $\sum_{i=1}^{n} \frac{n!}{i!}(-1)^{i+1}$

Therefore $P(B_0) = \frac{n! - D_n}{n!} = \sum_{i=2}^{n}\frac{ (-1)^{i}}{i!}$

• Maybe I'm missing something, but for n = 3: P(B0) is 2/3 (1/2 + 1/6) but your formula would seem to calculate 1/2 - 1/6 = 1/3.
– Foon
Commented Oct 11, 2017 at 14:07

By the Inclusion Exclusion principle, we have $$P(\cup A_i)=\sum P(A_i)-\sum P(A_i\cap A_j)+\ldots+(-1)^{n+1}\sum P(\cap A_i),$$

where $A_i$ is the event that the $i^{th}$ person picks his own hat.

A hint: $$P(A_1\cap A_2\cap\ldots\cap A_k)=\frac{(n-k)!}{n!}$$