This is a variation of a famous problem, that I have heard before but I have never seen it in this format before.
$N$ Guests arrive at a party, each wearing a hat. We collect all the hats and then randomly redistribute the hats, giving each person one of the $N$ has randomly. Letting $X_N$ be the number of hats that are matched correctly, what is the $PMF$ of $X_N$? I.e.
$P(X_N=k)=$
The common variations of this problem that I have seen usually involve the probability that no one gets the correct hat or as $N$ approaches $\infty$. I am struggling to identify a distribution that would result in any type of general formula for $PMF$ of this random variable. Has anyone seen this before?
Best Answer
Number of derangement of $n$ item has the following formula
$$D_n = n! \sum_{i=0}^n\frac{(-1)^i}{i!}$$
Let's consider how many cases that would satisfy $k$ hats being matched.
We first select $k$ people of which their hats are to be matched $\binom{N}{k}$ and then we compute the possible number of derangement for the other $N-k$ of the students, $D_{N-k}$
Hence \begin{align}Pr(X_N=k)&=\frac{\binom{N}{k}D_{N-k}}{N!} \\ &=\frac{\binom{N}{k}(N-k)!\sum_{i=0}^{N-k}\frac{(-1)^i}{i!}}{N!}\\ &=\frac{1}{k!}\sum_{i=0}^{N-k}\frac{(-1)^i}{i!}\end{align}