**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 the event that the*i*th man selects his own hat. Now, , the probability that at least one of the men selects his own hat, is given by*N*numbers, where the*i*th element is the number of the hat drawn by the*i*th man, then there are*N*! possible outcomes. [The outcome means, for example, that each man selects his own hat.] Furthermore, , the event that each of the*n*men 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*N*large is approximately equal to . 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*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*k*men, it follows that there are*k*of the men select their own hats. The desired probability is thus*N*large is approximately*e*^{-1}/*k*!.