A136300 -id:A136300 - cp's OEIS frontend

A136301 Frequency of occurrence for each possible "probability of derangement" for a Secret Santa drawing in which each person draws a name in sequence and the only person who does not draw someone else's name is the one who draws the final name.

1, 1, 1, 1, 5, 2, 1, 1, 13, 6, 13, 2, 6, 2, 1, 1, 29, 14, 73, 6, 42, 18, 29, 2, 18, 8, 14, 2, 6, 2, 1, 1, 61, 30, 301, 14, 186, 86, 301, 6, 102, 48, 186, 18, 102, 42, 61, 2, 42, 20, 86, 8, 48, 20, 30, 2, 18, 8, 14, 2, 6, 2, 1, 1, 125, 62, 1081, 30, 690, 330, 2069, 14, 414, 200, 1394

Offset: 3

Brian Parsonnet, Mar 22 2008

The sequence is best represented as a series of columns 1..n, where each column j has 2^(j-1) rows (see Example). For more details, see A136300.

The first column represents the case for 3 people (offset 3).

			Represented as a series of columns, where column j has 2^(j-1) rows, the sequence begins:
  row |j = 1   2   3   4   5 ...
  ----+-------------------------
    1 |    1   1   1   1   1 ...
    2 |        1   5  13  29 ...
    3 |        2   6  14  30 ...
    4 |        1  13  73 301 ...
    5 |            2   6  14 ...
    6 |            6  42 186 ...
    7 |            2  18  86 ...
    8 |            1  29 301 ...
    9 |                2   6 ...
   10 |               18 102 ...
   11 |                8  48 ...
   12 |               14 186 ...
   13 |                2  18 ...
   14 |                6 102 ...
   15 |                2  42 ...
   16 |                1  61 ...
   17 |                    2 ...
  ... |                  ... ...
.
If there are 5 people, numbered 1-5 according to the order in which they draw a name, and person #5 draws name #5, the first four people must draw 1-4 as a proper derangement, and there are 9 ways of doing so: 21435 / 23415 / 24135 / 31425 / 34125 / 34215 / 41235 / 43125 / 43215.
But the probability of each derangement depends on how many choices exist at each successive draw. The first person can draw from 4 possibilities (2,3,4,5). The second person nominally has 3 to choose from, unless the first person drew number 2, in which case person 2 may draw 4 possibilities (1,3,4,5), and so on. The probabilities of 21435 and 24135 are both then
        1/4 * 1/4 * 1/2 * 1/2 = 1/64.
More generally, if there are n people, at the i-th turn (i = 1..n), person i has either (n-i) or (n-i+1) choices, depending on whether the name of the person who is drawing has been chosen yet. A way to represent the two cases above is 01010, where a 0 indicates that the person's number is not yet drawn, and a 1 indicates it is.
For the n-th person to be forced to choose his or her own name, the last digit of this pattern must be 0, by definition. Similarly, the 1st digit must be a 0, and the second to last digit must be a 1. So all the problem patterns start with 0 and end with 10. For 5 people, that leaves 4 target patterns which cover all 9 derangements. By enumeration, that distribution can be shown to be (for the 3rd column = 5 person case):
        0-00-10 1 occurrences
        0-01-10 5 occurrences
        0-10-10 2 occurrences
        0-11-11 1 occurrences
1;
1, 1;
1, 5, 2, 1;
1, 13, 6, 13, 2, 6, 2, 1;
1, 29, 14, 73, 6, 42, 18, 29, 2, 18, 8, 14, 2, 6, 2, 1;

Brian Parsonnet, Table of n, a(n) for n = 3..257
Brian Parsonnet, Probability of Derangements

The application of this table towards final determination of the probabilities of derangements leads to sequence A136300, which is the sequence of numerators. The denominators are in A001044.
A048144 represents the peak value of all odd-numbers columns.
A000255 equals the sum of the bottom half of each column.
A000166 equals the sum of each column.
A047920 represents the frequency of replacements by person drawing at position n.
A008277, Triangle of Stirling numbers of 2nd kind, can be derived from A136301 through a series of transformations (see "Probability of Derangements.pdf").
Cf. A371761.

maxP = 15;
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)]]]];
TableForm[ Transpose[ sFreq ] ]
(* Code snippet to illustrate the conjectured connection with A371761: *)
R[n_] := Table[Transpose[sFreq][[2^n]][[r]], {r, n + 1, maxP - 1}]
For[n = 0, n <= 6, n++, Print[n + 1, ": ", R[n]]] (* Peter Luschny, Apr 10 2024 *)

H(r,c) = Sum_{j=0..c-L(r)-1} H(T(r), L(r)+j) * M(c-T(r)-1, j) where M(y,z) = binomial distribution (y,z) when y - 1 > z and (y,z)-1 when y-1 <= z and T(r) = A053645 and L(r) = A000523.

Conjecture: Assume the table represented as in the Example section. Then row 2^n is row n + 1 of A371761. - Peter Luschny, Apr 10 2024

Edited by Brian Parsonnet, Mar 01 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

A102263 Denominators of probabilities in gift exchange problem with n people.

Original entry on oeis.org

1, 4, 36, 144, 1800, 43200, 705600, 705600, 2116800, 127008000, 23051952000, 6638962176000, 280496151936000, 31415569016832000, 471233535252480000, 471233535252480000, 54474596675186688000, 3268475800511201280000

Offset: 2

Jerrold Grossman, Feb 17 2005

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. A102262, A136300.

See A102262 for formula for p(n).

More terms from Jon E. Schoenfield, Sep 30 2006

cp's OEIS Frontend

A136301 Frequency of occurrence for each possible "probability of derangement" for a Secret Santa drawing in which each person draws a name in sequence and the only person who does not draw someone else's name is the one who draws the final name.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

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

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Magma

Formula

Extensions

A102263 Denominators of probabilities in gift exchange problem with n people.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Formula

Extensions