1,4

In "Secret Santa", if a person picks his own name, he picks another name and throws his own name back in. If the last person draws his own name, there's a problem. What is the probability as a function of the number of people participating?

Brian Parsonnet, Probabilty of derangements

I have it built in Excel, not in symbolic notation. Here is a rough pass at a translation, but I still need to verify it for accuracy in this format. Numerator = 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. The excel file works, emailed to njas(AT)research.att.com.

If there is one person, the chance of the last person getting his 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 his 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.

Adjacent sequences: A136297 A136298 A136299 this_sequence A136301 A136302 A136303

Sequence in context: A132855 A051481 A011918 this_sequence A088756 A076215 A059856

frac,nonn,uned

Brian Parsonnet (bparsonnet(AT)comcast.net), Mar 22 2008