Matching Hats AND Coats Problem

Solution 1:

You can derive the probability in a manner similar to that for the usual derivation of the derangement probabilities (the probability that none of the $N$ men get their own hat back).

There are a total of $N!^n$ ways that all of the items can be distributed among the $N$ men so that each has exactly one of each type of item. Let $A_i$ denote the event that the $i$th man obtains the $n$ items that belong to him. The number of ways this can happen is $|A_i| = (N-1)!^n$, as this involves distributing all items but those belonging to the $i$th man among the other $N-1$ men. Similarly, $|A_i \cap A_j| = (N-2)!^n$, and, in general, $|A_{i_1} \cap A_{i_2} \cap \cdots \cap A_{i_j}| = (N-j)!^n$. There are also $\binom{N}{j}$ ways to choose which $j$ men will receive their own $n$ items.

Let $D(N,n,k)$ denote the number of ways that exactly $k$ of the $N$ men receive all $n$ of their items back. By the principle of inclusion/exclusion, $$D(N,n,0) = \sum_{j=0}^N (-1)^j \binom{N}{j} (N-j)!^n = N! \sum_{j=0}^N (-1)^j \frac{(N-j)!^{n-1}}{j!}.$$

Now, $D(N,n,k) = \binom{N}{k} D(N-k,n,0)$, as this is the number of ways of choosing $k$ of the $N$ men to receive all of their items back times the number of ways that none of the remaining $N-k$ men receive all of their items back. Thus $$D(N,n,k) = \binom{N}{k} (N-k)! \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!} = \frac{N!}{k!} \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!}.$$

Dividing by $N!^n$, we have that the probability that exactly $k$ of the $N$ men receive all $n$ of their items back is $$\frac{1}{k! N!^{n-1}} \sum_{j=0}^{N-k} (-1)^j \frac{(N-k-j)!^{n-1}}{j!}.$$

Note that this formula agrees with the values obtained by Henry for the case $N = 4$, $n=2$.

Added: In fact, the Poisson approximation suggested by Henry appears to match up well with the exact values provided by the formula given here for small values of $k$. The accuracy of the Poisson approximation appears to deteriorate, relatively speaking, as $k$ increases. However, the Poisson approach still gives a good absolute approximation when $k$ is large because the probabilities are extremely small.

Solution 2:

It is easier to work out the expected number of men with all their own items, namely $N^{-1}$ in the hat and coat case and $N^{1-n}$ in the more general case.

This is sampling without replacement, but as $N$ increases I would expect this to be asymptotically distributed like a Poisson distribution with the same expected values.

This asymptotic approximation is not bad even for small numbers. For 4 men and 2 items the expected number of men with the correct items is 0.25. The actual and Poisson probabilities, rounded to four decimal places, are

Correct actual  Poisson
0       0.7865  0.7788
1       0.1806  0.1947
2       0.0313  0.0243
3       0.0000  0.0020
4       0.0017  0.0001
5+      0       0.00001