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 factorialall 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)=(n1)(d(n1)+d(n2)). This is derived as follows:
A derangement of n objects can be obtained from a derangement of n1 objects by swapping the nth (last) object to be added with any one of the n1 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 n1 objects. The other derangements of n objects can be obtained by doing the swap with the already ordered list of n1 objects (therefore there are still n1 ways of doing this) and then deranging the remaining n2 (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 (n1)(d(n1)) + (n1)(d(n2)), or more simply (n1)(d(n1)+d(n2)).
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 nonrecursively 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 20031011 10:15:30 