<pre>
Q: 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?


A: 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! <code> (n!/((n-k)!'''k!))*(n-k)!/n! </code> 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)
</pre>
