Brian Parsonnet - cp's OEIS frontend

User: Brian Parsonnet

Brian Parsonnet has authored 2 sequences.

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

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.

Original entry on oeis.org

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

cp's OEIS Frontend

User: Brian Parsonnet

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions