2,3

n friends organize a gift exchange. The n names are put into a hat, and the first person draws one. If she picks her own name, then she returns it to the bag and draws again, repeating until she has a name that is not her own. Then the second person draws, again returning his own name if it is drawn. This continues down the line. What is the probability p(n) that when the n-th person draws, only her own name will be left in the bag?

I heard about the problem from Gary Thompson at Grove City College in PA.

As n increases, p(n) approaches 1/(n + log(n) + EulerGamma), where EulerGamma = .5772156649015... (the Euler-Mascheroni constant). - Jon E. Schoenfield (jonscho(AT)hiwaay.net), Sep 30 2006

p(n) = Sum_{ i = 1..n-2 } t(n,i) / (n-1)!^2,

where t(n,i) = (n-2)*i^2/(i-1)*t(n-1,i-1)-(n-i-2)*t(n-1,i) for 1<i<n-1;

t(n,1) = (-1)^(n-1)*(n-1)!/2 for i=1 and n>2;

t(n,i) = 0 otherwise. - Jon E. Schoenfield (jonscho(AT)hiwaay.net), Sep 30 2006

p(2) through p(10) are 0, 1/4, 5/36, 19/144, 203/1800, 4343/43200, 63853/705600, 58129/705600, 160127/2116800.

Cf. A102263.

Sequence in context: A145935 A024529 A106991 this_sequence A123281 A135171 A058765

Adjacent sequences: A102259 A102260 A102261 this_sequence A102263 A102264 A102265

nonn,frac

Jerry Grossman (grossman(AT)oakland.edu), Feb 17 2005

More terms from Jon E. Schoenfield (jonscho(AT)hiwaay.net), Sep 30 2006