# hat matching problem (Ross, p.41)

I'm studying Ross's probability book, and kind of got stuck on the matching problem.

Suppose that each of $N$ men at a party throws his hat into the center of the room. The hats are first mixed up, and then each man randomly selects a hat. What is the probability that none of the men select their own hat?

Solution(partial):

$P(\text{none of the men select their own hat})= 1- P( \text{at least one of the men select their own hat})$

Let: $E_i =$ the event that the ith man selects his own hat, $i=1, 2, \ldots, N$

$E_{i_1}E_{i_2}\dots E_{i_n}$ = the event that each of the $n$ men, $i_1,i_2,\ldots, i_n$, selects his own hat

the remaining $N-n$ men: the first can select any of $N-n$ hats, the second can then select any of $N-n-1$, and so on.

Therefore, there are $(N-n)!$ combinations of the event $E_{i_1}E_{i_2}\dots E_{i_n}$

My question is: It looks like the solution doesn't care whether there's a match among the remaining $N-n$ men. but, shouldn't we care? if there's one matched among the remaining $N-n$ men, it would be no longer be the event $E_{i_1}E_{i_2}\dots E_{i_n}$ ?

Any hint would be very appreciate, thank you!

• Please see Wikipedia, Derangements. Has also come up on MSE repeatedly. Commented Jul 17, 2014 at 4:07
• wow~ thanks! I'm now looking at it! :) Commented Jul 17, 2014 at 4:13
• You are welcome. Commented Jul 17, 2014 at 4:14
• As to your question, I hope the article, and/or MSE material, will make the Inclusion/Exclusion part of the argument clear. Commented Jul 17, 2014 at 4:17
• Recall the simplest cast: $|A \cup B| = |A| + |B| - |A \cap B|$. When computing $|A|$, you don't even have $B$ in mind. Similarly, $|B|$ has nothing to do with $A$. (Indeed, it if were easy to compute $|A \setminus B|$ and $|B \setminus A|$, then you wouldn't even need inclusion-exclusion.) Commented Nov 7, 2016 at 20:53

You're right, the solution focuses only on matches for a particular subset of the hats. This is a general feature of the inclusion-exclusion method: The probability that all conditions in some set $S$ hold is calculated from the probabilities for each subset $S'$ of all conditions in $S'$ holding, and in calculating that probability for $S'$ the conditions not contained in $S'$ are irrelevant.