Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Suppose $N$ men throw their hats in a room AND their coats in an other room. Each man then randomly picks a hat and a coat. What is the probability that:

  • None of the men select his own hat and his own coat
  • Exactly $k$ of the men select his own hat and his own coat.

More generally, if instead of $2$ items (hat and coat), the $N$ men threw $n$ items, how to find the probability mass function $P(k=0,1,2,\ldots,n)$ of the number of complete coincidences ($k$ men select their $n$ own items)?

share|improve this question

2 Answers 2

up vote 2 down vote accepted

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
share|improve this answer

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.

share|improve this answer
1  
Thank you very much. –  Jean-Pierre Apr 15 '11 at 18:14

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.