# Matching Problem

• Mar 29th 2010, 08:37 AM
Berge
Matching Problem
The Problem " Suppose that each man at a party throws his hat into the center of the room. The hats are first mixed up and then randomly selected. Whats the probability that exactly k of men select their own hats?"

The final Solution is (1-1+1/2!-1/3!+...+(-1)^n-k/(N-k)!)/k!
I know that the solution can be found by computing the complement of the probability of none of the men getting the matching hat, but it is not working. Why?
• Mar 29th 2010, 12:33 PM
Anonymous1
$\displaystyle E =$ event that no matches occurs. Denote $\displaystyle P_n = P(E).$
$\displaystyle M =$ event that the first man selects his own hat.

$\displaystyle P_n = P(E) = P(E|M)P(M) + P(E|M^c)P(M^c)$

$\displaystyle P(E|M) = 0,$
$\displaystyle P(M^{c}) = \frac{n-1}{n},$
$\displaystyle P_n = \frac{n-1}{n} P(E|M^c)$

$\displaystyle P(E|M^{c}) = \frac{1}{n-1}P_{n-2} + P_{n-1},$
$\displaystyle P_n = \frac{n-1}{n} P_{n-1}+\frac{1}{n} P_{n-2}.$

Identify the boundary conditions.
$\displaystyle P_1 = 0,$ $\displaystyle P_2 = 1/2.$

Prove $\displaystyle P_n$ by induction.
$\displaystyle P_n = \frac{1}{2!} - \frac{1}{3!} + \frac{1}{4!} - ... + \frac{(-1)^n}{n!}$

Now what is the compliment?
• Mar 29th 2010, 12:52 PM
Plato
The number of ways that none of the n gets his own hat is $\displaystyle n!\sum\limits_{j = 0}^n {\frac{{( - 1)^j }}{{j!}}}$.
For exactly k to get his hat, chose k: $\displaystyle \binom{n}{k}=\frac{n!}{(k!)(n-k)!}$.
Multiply that by $\displaystyle (n-k)!\sum\limits_{j = 0}^{n-k} {\frac{{( - 1)^j }}{{j!}}}$
To get the probability divide by $\displaystyle n!$