Secret Santa Perfect Loop problem
- (n) people put their name in a hat.
- Each person picks a name out of the hat to buy a gift for.
- If a person picks out themselves they put the name back into the hat.
- If the last person can only pick themselves then the loop is invalid and either
. start again
. or step back until a valid loop can be reached.
What is the probability that if n is 33 that the chain creates a perfect loop?
An example of a perfect loop where n is 4:
- A gives to B
- B gives to C
- C gives to D.
- D gives to A.
An example of a valid but not perfect loop where n is 4:
- A gives to B
- B gives to A
- C gives to D.
- D gives to C.
You are asking for the chance of a single cycle given that you have a derangement. For $n$ people, the number of derangements is the closest integer to $\frac {n!}e$ To have a cycle, person $1$ has $n-1$ choices, then that person has $n-2$ choices, then that person has $n-3$, etc. So there are $(n-1)!$ cycles. The odds are then (just about) $\frac e{n}$