# 401 probability/derangement.p

## Description

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?

probability/derangement.s

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: