|
%I #30 Dec 11 2021 02:34:50
%S 0,1,5,19,203,4343,63853,58129,160127,8885501,1500518539,404156337271,
%T 16040576541971,1694200740145637,24047240650458731,22823917472900053,
%U 2511014355032164231,143734030512459889193,49611557898193759558813,950601970122346247310883
%N Numerators of probabilities in gift exchange problem with n people.
%C This is a version of the Secret Santa game.
%C 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?
%C I heard about the problem from Gary Thompson at Grove City College in PA.
%H Jon E. Schoenfield, <a href="/A102262/b102262.txt">Table of n, a(n) for n = 2..389</a>
%H Math Forum at Drexel, <a href="http://mathforum.org/kb/message.jspa?messageID=6667330&tstart=0">A variant on the "Secret Santa"</a>
%F From _Jon E. Schoenfield_, Sep 30 2006: (Start)
%F p(n) = Sum_{i=1..n-2} t(n,i)/(n-1)!^2
%F where
%F 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;
%F t(n,1) = (-1)^(n-1)*(n-1)!/2 for i = 1 and n > 2;
%F t(n,i) = 0 otherwise.
%F (End)
%F 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
%e p(2) through p(10) are 0, 1/4, 5/36, 19/144, 203/1800, 4343/43200, 63853/705600, 58129/705600, 160127/2116800.
%o (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
%Y Cf. A102263, A136300.
%K nonn,frac
%O 2,3
%A _Jerrold Grossman_, Feb 17 2005
%E More terms from _Jon E. Schoenfield_, Sep 30 2006
|
