|
%I #43 Jun 02 2022 10:35:57
%S 1,0,1,5,76,1624,52116,2298708,133929216,9961180416,921248743680,
%T 103715841415680,13967643016085760,2217449301162071040,
%U 409861043056032503040,87262626872384643052800,21202798521768886355558400,5831660090586059239329792000,1802587564536011525042697830400
%N 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.)
%C 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?
%H Brian Parsonnet, <a href="/A136300/b136300.txt">Table of n, a(n) for n = 1..30</a>
%H Brian Parsonnet, <a href="/A136300/a136300_2.pdf">Probability of Derangements</a>
%F 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.
%F a(n) = (n-1)!*A102262(n)/A102263(n) for n > 1.
%e 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.
%t maxP = 22;
%t rows = Range[1, 2^(nP = maxP - 3)];
%t pasc = Table[
%t Binomial[p + 1, i] - If[i >= p, 1, 0], {p, nP}, {i, 0, p}];
%t sFreq = Table[0, {maxP - 1}, {2^nP}]; sFreq[[2 ;; maxP - 1, 1]] = 1;
%t For[p = 1, p <= nP, p++,
%t For[s = 1, s <= p, s++, rS = Range[2^(s - 1) + 1, 2^s];
%t sFreq[[p + 2, rS]] = pasc[[p + 1 - s, 1 ;; p + 2 - s]] .
%t sFreq[[s ;; p + 1, 1 ;; 2^(s - 1)]]]];
%t sProb = Table[p + 2 - BitGet[rows - 1, p - 1], {p, nP}];
%t sProb = Table[Product[sProb[[i]], {i, p}], {p, nP}]*
%t Table[If[r <= 2^p, 1, 0],
%t {p, nP}, {r, rows}];
%t rslt = Flatten[
%t Prepend[Table[sProb[[p]] . sFreq[[p + 2]], {p, nP}], {1, 0, 1}]]
%t prob = N[rslt/Array[(#1 - 1)!^2 & , maxP]] (* _Brian Parsonnet_, Feb 22 2011 *)
%Y The sequence frequency table (sFreq) is A136301.
%Y Cf. A000523, A053645, A102262, A102263.
%K nonn
%O 1,4
%A _Brian Parsonnet_, Mar 22 2008
%E Corrected and extended to a(19) by _Brian Parsonnet_, Feb 22 2011
|
