previous page: 400 probability/darts.p
page up: Puzzles FAQ
next page: 402 probability/family.p

401 probability/derangement.p


This article is from the Puzzles FAQ, by Chris Cole chris@questrel.questrel.com and Matthew Daly mwdaly@pobox.com with numerous contributions by others.

401 probability/derangement.p

12 men leave their hats with the hat check. If the hats are randomly
returned, what is the probability that nobody gets the correct hat?


Suppose we are handing out hats to n people. First we start with all
the possible outcomes. Then we subtract off those that assign the
right hat to a given person, for each of the n people. But this
double-counts each outcome that assigned 2 hats correctly, so we have
to add those outcomes back in. But now we've counted one net copy of
each outcome with 3 correct hats in our set, so we have to subtract
those off again. But now we've taken away each 4-correct-hat outcome
once too often, and have to put it back in, and so forth ... until we
add or subtract the outcome that involves all n people getting the
correct hats.

Putting it all in probabilities, the measure of the original set is 1.
For a given subset of k people, the probability that they all get
their correct hats is (n-k)!/n!, while there are (n choose k) such
subsets of k people altogether. But then

(n choose k)*(n-k)!/n! = (n!/((n-k)!*k!))*(n-k)!/n! = 1/k!

is the total probability measure we get by counting each subset of k
people once each. So we end up generating the finite series

1 - 1/1! + 1/2! - 1/3! +- ... +/- 1/n!

which is of course just the first n+1 terms of the Taylor series
expansion for f(x) = e^x centered at 0 and evaluated at -1, which
converges to 1/e quite fast. You can compute the exact probability for
any n >= 1 simply by rounding n!/e to the nearest whole number, then
dividing again by n!. Moreover I think you will find you are always
rounding down for odd n and rounding up for even n.

For example,

12! / e = 176214840.95798...

which is within 0.05 (absolute error, not relative) of the correct
intermediate result, 176214841.

Another fact is that if you set the probability of no matching hats
equal to m/n!, then m is an integer divisible by (n-1). That's
because the number of ways you can give hat #2 to person #1 is exactly
the same as the number of ways you can give that person hat #3,
likewise for hat #4, and so forth.

-- David Karr (karr@cs.cornell.edu)


Continue to:

previous page: 400 probability/darts.p
page up: Puzzles FAQ
next page: 402 probability/family.p