This site is supported by donations to The OEIS Foundation.

 Hints (Greetings from The On-Line Encyclopedia of Integer Sequences!)
 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^(n-1) 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(c-T(r)-1,j) for j = 0..c-L(r)-1, 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. EXAMPLE Say there are 5 people, named 1-5.  For the last person to choose #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 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 i-th turn (i = 1..N), person i has either (N-i) or (N-i+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 N-th 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):         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; 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 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 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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Last modified February 19 09:19 EST 2018. Contains 299330 sequences. (Running on oeis4.)