login
The OEIS is supported by the many generous donors to the OEIS Foundation.

 

Logo
Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A102262 Numerators of probabilities in gift exchange problem with n people. 3
0, 1, 5, 19, 203, 4343, 63853, 58129, 160127, 8885501, 1500518539, 404156337271, 16040576541971, 1694200740145637, 24047240650458731, 22823917472900053, 2511014355032164231, 143734030512459889193, 49611557898193759558813, 950601970122346247310883 (list; graph; refs; listen; history; text; internal format)
OFFSET

2,3

COMMENTS

This is a version of the Secret Santa game.

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.

LINKS

Jon E. Schoenfield, Table of n, a(n) for n = 2..389

Math Forum at Drexel, A variant on the "Secret Santa"

FORMULA

From Jon E. Schoenfield, Sep 30 2006: (Start)

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.

(End)

Based on the values of p(n) for n <= 1000, it seems plausible that, as n increases, p(n) approaches 1/(n + log(n) + EulerGamma), where EulerGamma = 0.5772156649015... (the Euler-Mascheroni constant). - Jon E. Schoenfield, Dec 11 2021

EXAMPLE

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

PROG

(Magma) N:=21; a:=[]; row:=[]; T:=[]; for n in [2..N] do row[n-1]:=0; T[n]:=row; T[n][1]:=(-1)^(n-1)*Factorial(n-1) div 2; for i in [2..n-2] do T[n][i]:=(n-2)*i^2/(i-1)*T[n-1][i-1]-(n-i-2)*T[n-1][i]; end for; p:=0; for i in [1..n-2] do p+:=T[n][i]/Factorial(n-1)^2; end for; a[#a+1]:=Numerator(p); end for; a; // Jon E. Schoenfield, Dec 10 2021

CROSSREFS

Cf. A102263, A136300.

Sequence in context: A145935 A024529 A106991 * A123281 A135171 A058765

Adjacent sequences:  A102259 A102260 A102261 * A102263 A102264 A102265

KEYWORD

nonn,frac

AUTHOR

Jerrold Grossman, Feb 17 2005

EXTENSIONS

More terms from Jon E. Schoenfield, Sep 30 2006

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recents
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified September 27 18:50 EDT 2022. Contains 357062 sequences. (Running on oeis4.)