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