Secret Santa 


There are many Secret Santa problems. The one we're interested in here is this:

So I've been doing some calculations, and here are the results:
participants  of failure  
  
  
  
  
  
  
  
  
  
  
  
 
These results match exactly those of the simulations I've been running, so I know they're right. They are strange numbers, though, so where do they come from?
Being so strange you might imagine that the calculations aren't simple or straightforward, and they're not. The calculation for N=1, 2 or 3 aren't very enlightening. Here's the full calculation for N=4.
We're choosing from A, B, C and D. A can't go first, so we have three choices, and they're equally likely. Here's a table for the next choice:
Chosen  Next choices 
B  A, C, D 
C  A, D 
D  Don't care 
In the last case we don't care because we're trying to compute the probability of the process failing. With D selected it can't fail.
But now we have 5 ways to continue: BA, BC, BD, CA, CD, and their probabilities are not equal:
Chosen  Prob  Next 
BA  1/3 * 1/3  D 
BC  1/3 * 1/3  A, D 
BD  1/3 * 1/3  A 
CA  1/3 * 1/2  B, D 
CD  1/3 * 1/2  A, B 
We only care if we get D last, so the only options we get are BCAD and CABD. The probabilities of these are $\frac{1}{3}*\frac{1}{3}*\frac{1}{2}$ and $\frac{1}{3}*\frac{1}{2}*\frac{1}{2}.$
Now we can see that the probability of failing is $\frac{1}{18}*\frac{1}{12}$ which is $\frac{5}{36}.$

And that's what makes the calculations so very difficult.
I've written a program to compute the results precisely, but there's very little insight to be gained from them. Each takes longer than the previous, and it's not fast. The case N=12 took 53 minutes, the next is computed to take 12.5*53 minutes, or about 11 hours.
Or so.
The next stage will be to try to find a recurrence formula for the problem, but I've not had time to work on that yet. If anyone has a clean recurrence formula then I'd love to hear from you, otherwise this puzzle will continue to occupy my occasional free moments.