Problem 75 Solution

Lets take the case of 12 people for example.

There are 12! ways of drawing names.

Next determine the number of these 12! ways that have no matches.

Subtract from 12! the number of ways that one person matches, which would be 12*11! (12 people times 11! ways to arrange the other 11 names).

However this would be double counting those combinations in which two people match, which is (12:2)*10! = 12!/2!. Note that (x:y) means x choose y or x!/(y!*(x-y)!). So add this group back in.

Yet we must take out from those we put in those combinations in which three people match, which is (12:3)*9! = 12!/3!.

So keep repeating this process and the numerator or number of combinations in which there are no matches is 12! - 12! + 12!/2! - 12!/3! + 12!/4! - 12/5! ... + 12!/12!.

Divide this by the total number of combinatios, 12!:

1 - 1 + 1/2! - 1/3! + 1/4! - 1/5! ... +1/12!.

This same method works for any n.

Note that it approaches 1/e.

Michael Shackleford, ASA