# The Matching Problem: Probability of At Least One Man Selecting His Own Hat

I came across this example question in this book (Full Solution on pg56)by Sheldon Ross there are some intermediate steps in this problem that have stumped me.

The Question & Book Explanation:

Suppose that each of the N men at a party throws his hat into the center of the room, then each man randomly selects a hat. What is the probability that none of the men selects his own hat?

The probability that at least one man selects his own hat is given by the generalised inclusion exclusion principle: $$P( \bigcup_{i=1}^{N}E_i) = \sum_{i=1}^{N} P(E_i) - \sum_{i_1 < i_2} P(E_{i_1}E_{i_2})+ ... +(-1)^{n+1} + \sum_{i_1 < i_2 <...< i_3} P(E_{i_1}E_{i_2}...E_{i_n})+...+(-1)^{N+1}P(E_{1}E_{2}...E_{i_N})$$

The following text is taken from the book:

"If we regard the outcome of this experiment as a vector of N numbers, where the ith element is the number of the hat drawn by the ith man, then there are N! possible outcomes. [The outcome $$(1, 2, 3, ... , N)$$ means, for example, that each man selects his own hat.] Furthermore, $$E_{i_1}E_{i_2} ... E_{i_n}$$, the event that each of the n men $$i_1, i_2, ... , i_n$$ selects his own hat, can occur in any of $$(N − n)(N − n − 1)··· 3 · 2 · 1 = (N − n)!$$ possible ways; for, of the remaining $$N − n$$ men, the first can select any of N − n hats, the second can then select any of $$N − n − 1$$ hats, and so on. Hence, assuming that all N! possible outcomes are equally likely, we see that

$$P(E_{i_1} E_{i_2} E_{i_3} ... E_{i_n}) = \frac{(N-n)!}{N!}$$ "

My Doubts:

1. How can $$E_{i_1}E_{i_2} ... E_{i_n}$$, the event that each of the n men $$i_1, i_2, ... , i_n$$ selects his own hat, occur in $$(N-n)!$$ ways? I'm sorry if this is a stupid question but if out of 15 people (N), 8 people(n) are selecting their own hat, then how can they do so in $$(15 - 8)! = 7!$$ ways? Is it because those 8 people are considered as a single entity and the remaining 7 are arranged around them in $$7!$$ ways?

Any help would be extremely appreciated!

• That last formula is the probability that any one particular set of $n$ people all get their own hats, when it's used in the overall problem there is a sum of such terms over all size $n$ subsets of the whole group.
– Ned
Commented Jan 10, 2022 at 20:32
• Commented Jan 10, 2022 at 20:40
• @user2661923. In the Wiki article, after about 40 lines we finally see the formula $N!\sum_{j=0}^N(-1)^j/j!$.... I would have started with it. Commented Jan 10, 2022 at 22:10
• This is covered in the book "101 Great Problems In Elementary Mathematics" by H. Dorrie. Commented Jan 10, 2022 at 22:15
• Had a similar question about the same book a moment ago. In case it helps anyone in the future: knowing 8 of the 15 people get their own hat doesn't preclude some of the remaining 7 from getting their own hat, too. Commented Apr 9 at 19:56

Consider this: instead of 15 people I will choose 16 as $$N$$, so for the example, I can enumerate each of the 16 hats $$i_n$$ with the name of their owner, labeling each of them with an hexadecimal symbol $$0$$ to $$9$$ and then $$A$$ to $$F$$ (it just a label, but is to identify each person with just one character uniquely, an hexadecimals are a wide known list of labels so is less to explain)... so, any random pick of hats could be arranged as a word of 16 hexadecimal characters $$i_1 i_2 i_3 \cdots i_{15} i_{16}$$ that will look like $$123456789ABCDEF$$ if everyone take its own hat, or as a random combination of these symbols without repetition of them for other combinations...
now, if 8 persons picks each of their hats, the question is equivalent to order the following string $$12345678xxxxxxx$$ where are only $$7$$ symbols left to make the different combinations, and since each hat is picked just only once, the next person can choose among 7 hats, but the next one only can choose from $$6$$ since the previous hat is already taken, and so on, the possible combinations left after the 8 persons picked their own hats (which determines the first symbols in an unique array), the remaining options for the string are $$7!$$ ways.