Suppose there are n people in an office. At Christmas they have a random gift exchange in which every name is writen on scraps of paper, mixed around in a hat, and then everyone draws a name at random to determine who they are to get a gift for.

What is the probability nobody draws their own name?

Define n choose k as the number of distinct combinations of n elements taken k at a time. Denote n choose k as (n k) = n!/k!(n-k)! There are n! possible outcomes, now how many outcomes are such that no one draws there own name? Start with n! subtract from that the number of drawings such that one person draws there name. However we now are counting twice the situation where two people draw there own names so we must add this back in. Ups... We added back in those outcomes where three people match, get the idea, alternate until you hit n... Thus prob is the series Sum(k=0 to k=n) of (-1)^(k)*(n-k)!*(n k)/n! = Sum(k=0 to k=n) (-1)^k/k! and of course via taylor lim n-> infinity = e^(-1)

Posted by Hal9000 on 2003-10-12 14:10:12