

A136301


Frequency of occurrence for each possible "probability of derangement" for a Secret Santa drawing in which each person draws a name in sequence but is not allowed to pick his own name, and for which the last person does draw his own name.


3



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
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

3,5


COMMENTS

The sequence is best represented as a series of columns 1..n, where each column n has 2^(n1) rows. For more detail, see A136300
The first column represents the case for 3 people (offset 3)


LINKS

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


FORMULA

H(r,c) = sum of H(T(r),L(r)+j) * M(cT(r)1,j) for j = 0..cL(r)1, where M(y,z) = binomial distribution (y,z) when y  1 > z and (y,z)1 when y1 <= z and T(r) = A053645 and L(r) = A000523.


EXAMPLE

Say there are 5 people, named 15. For the last person to choose #5, the first four people must draw 14 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 probability 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 ith turn (i = 1..N), person i has either (Ni) or (Ni+1) choices, depending on whether his own name is 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 Nth person to be forced to choose his 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):
00010 1 occurrences
00110 5 occurrences
01010 2 occurrences
01111 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;


MATHEMATICA

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)]]]];
TableForm[ Transpose[ sFreq ] ]


CROSSREFS

The application of this table towards final determination of the probabilities of derangements leads to sequence A136300, which is the series of numerators. The denominators are A001044.
A048144 represents the peak value of all oddnumbers 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 transformation (see "Probability of Derangements.pdf")
Sequence in context: A180133 A197419 A029764 * A132690 A089086 A238716
Adjacent sequences: A136298 A136299 A136300 * A136302 A136303 A136304


KEYWORD

uned,nonn,tabf


AUTHOR

Brian Parsonnet, Mar 22 2008


EXTENSIONS

Edited by Brian Parsonnet, Mar 01 2011


STATUS

approved



