

A136300


Numerator of ratio (the denominator being (n1)!^2 = A001044(n1)) 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.)


4



1, 0, 1, 5, 76, 1624, 52116, 2298708, 133929216, 9961180416, 921248743680, 103715841415680, 13967643016085760, 2217449301162071040, 409861043056032503040, 87262626872384643052800, 21202798521768886355558400, 5831660090586059239329792000, 1802587564536011525042697830400
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,4


COMMENTS

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?


LINKS



FORMULA

Sum of H(i, N2) * X(i, N2) for i=0..2^(N3), N is the number of people and H(r,c) = sum of H(T(r),L(r)+j) * M(cT(r)1,j) for j = 0..cL(r)1 and X(r,c) = product of (3 + k  b(r,k)) for k = 0..(c2) and M(y,z) = binomial distribution (y,z) when y  1 > z and (y,z)1 when (y1)<=z and b(r,k) = bit k of r in base 2 and T(r) = A053645 and L(r) = A000523.


EXAMPLE

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.


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)]]]];
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 *)


CROSSREFS

The sequence frequency table (sFreq) is A136301.


KEYWORD

nonn


AUTHOR



EXTENSIONS



STATUS

approved



