A Loopy Holiday Gift Exchange

In a class gift exchange, everyone puts their own name in a hat and then each student draws a name. If anyone ever draws their own name, the whole class restarts. Once a valid draw is complete, the “who buys for whom” arrangement splits into loops. With five students, how likely is it that the whole class forms a single loop?

The Fiddler, Zach Wissner-Gross, November 21, 2025(original post)

Solution

Restarting whenever someone draws their own name means the final arrangement is a uniformly random derangement: a permutation with no fixed points. A single loop covering everyone is a single $5$-cycle. There are $(5-1)! = 24$ cycles on five elements, and the number of derangements of five is $D_5 = 44$, so $$P(\text{single loop}) = \frac{4!}{D_5} = \frac{24}{44} = \frac{6}{11} \approx \boxed{54.5\%}.$$

The computation

Enumerate every derangement of five (no one draws their own name) and count the fraction that form one big cycle, by walking the arrangement from a starting student and checking it visits all five before closing.

from itertools import permutations
from fractions import Fraction as F
ders = [p for p in permutations(range(5)) if all(p[i] != i for i in range(5))]
def single_loop(p):
    seen = set(); i = 0
    while i not in seen: seen.add(i); i = p[i]
    return len(seen) == 5
print(F(sum(single_loop(p) for p in ders), len(ders)))   # 6/11

Extra Credit

With $N$ students (a large number), how likely is a single loop, in terms of $N$?

Solution

A single loop is one of the $(N-1)!$ full cycles, out of $D_N$ derangements, so $$P(\text{single loop}) = \frac{(N-1)!}{D_N}.$$ Since $D_N = N!\sum_{k=0}^{N}\tfrac{(-1)^k}{k!} \to \tfrac{N!}{e}$, this becomes $$\frac{(N-1)!}{N!/e} = \frac{e}{N} = \boxed{\frac{e}{N}}$$ in the large-$N$ limit. (At $N=10$ it already equals $e/10$ to six places.)

The computation

Form the exact ratio of full cycles $(N-1)!$ to derangements $D_N$ (built from its recurrence) for growing $N$, and watch it close on $e/N$.

from math import factorial, e
def D(n):                          # derangements via the standard recurrence
    a, b = 1, 0
    for k in range(2, n + 1): a, b = b, (k - 1)*(a + b)
    return b
for N in (5, 10, 200):
    print(N, factorial(N - 1)/D(N), e/N)