A102263 -id:A102263 - cp's OEIS frontend

A136300 Numerator of ratio (the denominator being (n-1)!^2 = A001044(n-1)) giving the probability that the last of n persons drawing names randomly from a set of names draws their own, given that each person previously has drawn in succession and did not keep their own name. (Probability of derangements when allocated / rejected sequentially.)

1, 0, 1, 5, 76, 1624, 52116, 2298708, 133929216, 9961180416, 921248743680, 103715841415680, 13967643016085760, 2217449301162071040, 409861043056032503040, 87262626872384643052800, 21202798521768886355558400, 5831660090586059239329792000, 1802587564536011525042697830400

Offset: 1

Brian Parsonnet, Mar 22 2008

nonn

In "Secret Santa", if a person picks their own name, they pick another name and they throw their own name back in. If the last person draws their own name, there's a problem. What is that probability as a function of the number of people participating?

			If there is one person, the chance of the last person getting their own name is 100%, or 1 over 0!^2. For 2 people, it is 0 / 1!^2. For 3 people, it is 1 / 2!^2, creating a more interesting case. The possible drawings are {2,1,3}, {2,3,1} and {3,1,2}. All other drawings can't happen because the name is rejected and redrawn. But these 3 outcomes don't have equal probability, rather, they are 25%, 25% and 50% respectively. The first outcome is the only one in which the last person draws their own name. The first person has a 50% chance of drawing a 2 or 3. If 2, the second person has a 50% chance of drawing 1 or 3, for a total outcome probability of 1/4. Similarly with 4 people, the chance is 5/36, followed by 76/576 for 5 people, etc. For the case of 5 people, the above equations boil down to this end calculation: {1,5,2,1} * {12,8,9,6} summed, or 12 + 40 + 18 + 6 = 76.

Brian Parsonnet, Table of n, a(n) for n = 1..30
Brian Parsonnet, Probability of Derangements

The sequence frequency table (sFreq) is A136301.

Cf. A000523, A053645, A102262, A102263.

maxP = 22;
rows = Range[1, 2^(nP = maxP - 3)];
pasc = Table[
   Binomial[p + 1, i] - If[i >= p, 1, 0], {p, nP}, {i, 0, p}];
sFreq = Table[0, {maxP - 1}, {2^nP}]; sFreq[[2 ;; maxP - 1, 1]] = 1;
For[p = 1, p <= nP, p++,
  For[s = 1, s <= p, s++, rS = Range[2^(s - 1) + 1, 2^s];
        sFreq[[p + 2, rS]] = pasc[[p + 1 - s, 1 ;; p + 2 - s]] .
            sFreq[[s ;; p + 1, 1 ;; 2^(s - 1)]]]];
sProb = Table[p + 2 - BitGet[rows - 1, p - 1], {p, nP}];
sProb = Table[Product[sProb[[i]], {i, p}], {p, nP}]*
   Table[If[r <= 2^p, 1, 0],
         {p, nP}, {r, rows}];
rslt = Flatten[
  Prepend[Table[sProb[[p]] . sFreq[[p + 2]], {p, nP}], {1, 0, 1}]]
prob = N[rslt/Array[(#1 - 1)!^2 & , maxP]] (* Brian Parsonnet, Feb 22 2011 *)

Sum of H(i, N-2) * X(i, N-2) for i=0..2^(N-3), N is the number of people and H(r,c) = sum of H(T(r),L(r)+j) * M(c-T(r)-1,j) for j = 0..c-L(r)-1 and X(r,c) = product of (3 + k - b(r,k)) for k = 0..(c-2) and M(y,z) = binomial distribution (y,z) when y - 1 > z and (y,z)-1 when (y-1)<=z and b(r,k) = bit k of r in base 2 and T(r) = A053645 and L(r) = A000523.

a(n) = (n-1)!*A102262(n)/A102263(n) for n > 1.

Corrected and extended to a(19) by Brian Parsonnet, Feb 22 2011

A102262 Numerators of probabilities in gift exchange problem with n people.

Original entry on oeis.org

0, 1, 5, 19, 203, 4343, 63853, 58129, 160127, 8885501, 1500518539, 404156337271, 16040576541971, 1694200740145637, 24047240650458731, 22823917472900053, 2511014355032164231, 143734030512459889193, 49611557898193759558813, 950601970122346247310883

Offset: 2

Jerrold Grossman, Feb 17 2005

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.

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

Jon E. Schoenfield, Table of n, a(n) for n = 2..389
Math Forum at Drexel, A variant on the "Secret Santa"

Cf. A102263, A136300.

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

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

More terms from Jon E. Schoenfield, Sep 30 2006

cp's OEIS Frontend

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions