Matching Problem

**Berge** · March 29th 2010, 08:37 AM

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?

**Anonymous1** · March 29th 2010, 12:33 PM

$E =$ event that no matches occurs. Denote $P_n = P(E).$
$M =$ event that the first man selects his own hat.

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

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

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

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

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

Now what is the compliment?

**Plato** · March 29th 2010, 12:52 PM

The number of ways that none of the n gets his own hat is $n!\sum\limits_{j = 0}^n {\frac{{( - 1)^j }}{{j!}}}$ .
For exactly k to get his hat, chose k: $\binom{n}{k}=\frac{n!}{(k!)(n-k)!}$ .
Multiply that by $(n-k)!\sum\limits_{j = 0}^{n-k} {\frac{{( - 1)^j }}{{j!}}}$
To get the probability divide by $n!$

Thread: Matching Problem

LinkBack

Thread Tools

Display

Matching Problem

Similar Math Help Forum Discussions

[SOLVED] Pigeonhole principle and minimum numbers of socks matching problem related

Stable Matching

Local max/ min matching definition? problem

Pattern matching?

Matching problem

Search Tags