login
This site is supported by donations to The OEIS Foundation.

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

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 = 1..255

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 | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

Content is available under The OEIS End-User License Agreement .

Last modified September 22 20:29 EDT 2014. Contains 247085 sequences.