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:
- 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!
Best Answer
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.
Surely there are better explanations, but I have choose explicitly to do one by modeling the problem as a string of characters to be arranged, because I do have a lot of difficulty when modelling and understanding probability problems, and abstracting the problem into string's characters arrangement make it easy for me to understand them... hope it helps you too.