The Matching Problem 配對理論

Example (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.
(a) What is the probability that none of the men selects his own hat?
(b) What is the probability that exactly k of the men select their own hats?
Solution:
(a)
We first calculate the complementary probability of at least one man's selecting his own hat. Let us denote by $E_i,i=1,2,\ldots ,N$ the event that the ith man selects his own hat. Now, $\displaystyle P\left (\bigcup^N_{i=1}E_i\right )$, the probability that at least one of the men selects his own hat, is given by
$\begin{array}{rcl} \displaystyle P\left (\bigcup^N_{i=1}E_i\right )&=& \display... ...dots E_{i_n})\\ \\ &&+\cdots +(-1)^{N+1}P(E_1E_2\cdots E_N) \\ \\ \end{array}$
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,\ldots ,N)$ means, for example, that each man selects his own hat.] Furthermore, $E_{i_1}E_{i_2}\ldots E_{i_n}$, the event that each of the n men $i_1,i_2,\ldots ,i_n$ selects his own hat, 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
$\displaystyle P(E_{i_1}E_{i_2}\cdots E_{i_n})=\frac{(N-n)!}{N!}$
Also, as there are ${N\choose n}$ terms in $\displaystyle\sum_{i_1<i_2\cdots <i_n}P(E_{i_1}E_{i_2}\cdots E_{i_n})$, we see that
$\displaystyle\sum_{i_1<i_2\cdots <i_n}P(E_{i_1}E_{i_2}\cdots E_{i_n})= \frac{N!(N-n)!}{(N-n)!n!N!}=\frac{1}{n!}$
and thus
$\displaystyle P\left (\bigcup^N_{i=1}E_i\right ) =1-\frac{1}{2!}+\frac{1}{3!}-\cdots +(-1)^{N+1}\frac{1}{N!}$
Hence the probability that none of the men selects his own hat is
$\displaystyle1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1)^N}{N!}$
which for N large is approximately equal to $e^{-1}\approx .36788$. In other words, for N large, the probability that none of the men selects his own hat is approximately .37.
(b)
To obtain the probability that exactly k of the N men select their own hats, we first fix attention on a particular set of k men. The number of ways in which these and only these k men can select their own hats is equal to the number of ways in which the other N-k men can select among their hats in such a way that none of them selects his own hat. But, as
$\displaystyle1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1)^{N-k}}{(N-k)!}$
is the probability that not one of N-k men, selecting among their hats, selects his own, it follows that the number of ways in which the set of men selecting their own hats corresponds to the set of k men under consideration is
$\displaystyle(N-k)!\left [1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots + \frac{(-1)^{N-k}}{(N-k)!}\right ]$
Hence, as there are ${N\choose k}$ possible selections of a group of k men, it follows that there are
$\displaystyle{N\choose k}(N-k)!\left [1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots + \frac{(-1)^{N-k}}{(N-k)!}\right ]$
ways in which exactly k of the men select their own hats. The desired probability is thus
$\displaystyle\frac{{N\choose k}(N-k)!\left [1-1+\frac{1}{2!}-\frac{1}{3!}+\cdot... ...N!} =\frac{1-1+\frac{1}{2!}-\frac{1}{3!}+\cdots +\frac{(-1)^{N-k}}{(N-k)!}}{k!}$
which for N large is approximately e-1/k!.          $\rule[0.02em]{1.0mm}{1.5mm}$