Suppose that each of $n$ men at a party throws his hat into the center of the room. The hats are mixed up and then each man randomly selects a hat. What is the probability that at least one of the men selects his own hat?
[Math] Suppose that each of $n$ men at a party throws his hat into the center of the room…
derangementsprobability
Related Solutions
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.
One thing that is sometimes helpful is to write a computer program to run a lot of random trials and see if the number produced by the computer is way off the number you expect. For example:
# This is a Perl program
my $hats = shift || 8;
my $trials = shift || 10000;
my $derangements = 0;
TRIAL:
for (1..$trials) {
my @perm = ("dummy", permute(1..$hats));
for $hat (1..$hats) {
if ($perm[$hat] == $hat) { next TRIAL }
}
$derangements++;
}
print "In $trials trials, there were $derangements cases in which nobody got their own hat.\n";
printf "That's %5.2f%%.\n", $derangements * 100 / $trials;
sub permute {
my @items = @_;
# Fischer-Yates algorithm
for my $n (reverse 0 .. $#items) {
my $m = int rand($n + 1);
@items[$n,$m] = @items[$m,$n] if $m != $n;
}
return @items;
}
This prints:
In 10000 trials, there were 3683 cases in which nobody got their own hat. That's 36.83%.
This is far enough from your suggested value of $\frac78\frac67\ldots\frac12 = \frac18 = 12.5\%$ that we can be sure that that is wrong or that the program has a severe error.
(In fact, 36.83% is close to the theoretically correct value, which happens to be $2119\over 5760$.)
Best Answer
It has to do with derangements: $n!-D(n)$.
Look here: https://en.wikipedia.org/wiki/Derangement