
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 (11+1/2!1/3!+...+(1)^nk/(Nk)!)/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?

$\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(EM)P(M) + P(EM^c)P(M^c)$
$\displaystyle P(EM) = 0,$
$\displaystyle P(M^{c}) = \frac{n1}{n},$
$\displaystyle P_n = \frac{n1}{n} P(EM^c)$
$\displaystyle P(EM^{c}) = \frac{1}{n1}P_{n2} + P_{n1},$
$\displaystyle P_n = \frac{n1}{n} P_{n1}+\frac{1}{n} P_{n2}.$
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?

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!)(nk)!}$.
Multiply that by $\displaystyle (nk)!\sum\limits_{j = 0}^{nk} {\frac{{(  1)^j }}{{j!}}} $
To get the probability divide by $\displaystyle n!$