Secret Santa Perfect Loop problem

Question

1. (n) people put their name in a hat.
2. Each person picks a name out of the hat to buy a gift for.
3. If a person picks out themselves they put the name back into the hat.
4. 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.

Answer 1

Let $P_N$ be the probability to obtain a perfect loop with $N$ participants.

$ A \rightarrow C \rightarrow B \rightarrow D \rightarrow A $
$ A \rightarrow B \rightarrow D \rightarrow C \rightarrow A $
$ C \rightarrow A \rightarrow B \rightarrow D \rightarrow C $
are perferct loops.
We can see that the second and third one describe the same loop, so we can count the total number of perfect loops by counting all the possible permutations of C, B and D. In the same manner, we find that the number of perfect loops with N participants is $(N-1)!$

Thus, $P_N = \frac{(N-1)!}{n(\Omega)} $

The sample space are all possible loops such as everyone has been asigned a different name than his own, which is in other words, the total number of possible derangments.

The number of derangments of n items, $d(N)$, is given by

$d(N) = N! \sum_o^N\frac{(-1)^i}{i!}$

And so,

$P_N = \frac{(N-1)!}{d(N)} = \frac{1}{N \sum_o^N\frac{(-1)^i}{i!}} $

For $N = 33$,

$P_N = \frac{8222838654177922817725562880000000}{3194414033122656019847107490716704992}$

Answer 2

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}$

Answer 3

In order to count the number of perfect loops with $n$ people, we need to count the number of distinct labelings of a cycle on $n$ vertices, say $c(n)$. While I don't have a proof yet, I think the number is given by $$ c(n)=\frac{1}{2n-3}\binom{3n-6}{n-2}. $$ On the other hand, to count the number of valid loops we want to know the number of ways to partition $n$ that does not include 1, say $p'(n)$. That is given by the generating function $$ \sum_{n=1}^\infty p'(n)x^n=\prod_{n=2}^\infty\frac{1}{1-x^n}. $$ Then for each partition we would need to count the number of perfect loops admitted using our previous equation.

For example the number of valid loops involving 5 people would be $$\binom{5}{3}c(3)\binom{2}{2}c(2).$$ And so the probability for picking a perfect loop on 5 people from the number of valid loops on 5 people would be $$ \frac{c(5)}{c(5)+\binom{5}{3}c(3)\binom{2}{2}c(2)}. $$

Good luck extending this to $n=33$.