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?

This is the same as having two lists of names and one of them is shuffled to a random permutation. Some of the permutations will result in one or more names finding itself in its initial position and therefore matching at that/those spots, the unshuffled list; other permutations will result in no such matches. Such permutations, resulting in no matches, are called derangements.

Call the number of derangements of n things d(n). The number of permutations of n things is n! (n factorial--all the integers from 1 to n multiplied together). The probability of no match, the answer to this question, is d(n)/n!.

There is a recursive formula for d(n): d(n)=(n-1)(d(n-1)+d(n-2)). This is derived as follows:

A derangement of n objects can be obtained from a derangement of n-1 objects by swapping the nth (last) object to be added with any one of the n-1 objects in the older derangement. But this results in only one subset of the derangements of the new set of n object: that is, those derangements in which the last position is occupied by the object other than the one originally in the spot now occupied by piece number n as it is based on a strict derangement of the n-1 objects. The other derangements of n objects can be obtained by doing the swap with the already ordered list of n-1 objects (therefore there are still n-1 ways of doing this) and then deranging the remaining n-2 (not the last position as we want that to have the object from the position currently occupied by piece number n, and not object n itself). Thus it's (n-1)(d(n-1)) + (n-1)(d(n-2)), or more simply (n-1)(d(n-1)+d(n-2)).

This is the series mentioned in the Sequences puzzle Next in Line.

This sequence of numbers, 0,1,2,9,44,265,... (for n=1,2,3...) can be obtained non-recursively based on the fact that it quickly approaches n!/e where e is 2.71828..., the base of the natural logarithms. Each one in fact is n!/e rounded to the nearest integer, or in mathematical terms [n!/e + 1/2] where the square brackets indicate the floor function; the addition of 1/2 turns it into the normal rounding function.

So the final probability can be given by [n!/e + 1/2] / n!. As the number of participants gets into the teens it quickly approaches 1/e.

Posted by Charlie on 2003-10-11 10:15:30