Derangements: The Math Behind Secret Santa

The rule "nobody draws themselves" sounds trivial — shuffle the names and check — but it hides a counting problem mathematicians have chased for three centuries. The assignments you need are called derangements, and their arithmetic explains why Secret Santa draws fail, why mutual pairs keep appearing, and how a computer finds a valid draw with exclusions in milliseconds.

What a derangement is

A permutation is any rearrangement of a list. A derangement is a permutation with no fixed points — no element left in its original position. Translated to gift exchanges: every giver points at a different person, nobody draws themselves, and because everyone appears exactly once as giver and once as receiver, it is a perfect one-to-one mapping. For four people Alice, Bob, Carol and Dave, one derangement is Alice→Bob, Bob→Carol, Carol→Dave, Dave→Alice (a single 4-cycle); another splits into two swaps, Alice↔Bob and Carol↔Dave. Both are legal draws; they feel different socially, which matters later.

Counting derangements: the !n operator

The number of derangements of n items gets its own notation: !n (the subfactorial). The values start !1 = 0, !2 = 1, !3 = 2, !4 = 9, !5 = 44, !6 = 265, and grow roughly by multiplying by n each step. A tidy recurrence — !n = (n−1)(!(n−1) + !(n−2)) — generates them, and the exact formula is

!n = n! · (1 − 1/1! + 1/2! − 1/3! + … ± 1/n!)

For ten people that's 1,334,961 legal draws out of 3,628,800 total orderings. The alternating series is where a famous constant sneaks in.

The surprising role of e

As n grows, the proportion of permutations that are derangements converges to 1 − 1/e ≈ 63.2%. In other words, if you shuffle names at random and hope nobody drew themselves, you succeed about 63% of the time — the same 1−1/e that appears in the hat-check problem: throw n hats randomly back at n owners and the expected number of correct hats is exactly 1, forever, for any n. This is why the "shuffle and re-shuffle until valid" strategy works fine in practice (you rarely need more than two tries), but a constrained search is cleaner: it either returns a valid draw or proves none exists.

Why two people keep drawing each other

Mutual pairs (Alice↔Bob) are perfectly legal derangements, and in a random draw they appear often: the probability that Alice and Bob form a two-cycle is 1/(n(n−1)), summed over all pairs that's roughly a 50% chance a 10-person draw contains at least one mutual pair. For couples and office romances this is exactly the outcome groups want to avoid — hence the standard advice to add exclusions. Exclusions transform the problem from a shuffle into a constraint satisfaction problem: build the assignment one giver at a time, skipping forbidden receivers, and when a path dead-ends, undo the last choice and try another — backtracking, the same engine that solves sudoku.

When a draw is truly impossible

Exclusions can make any valid assignment vanish. The minimal impossible case is two people who exclude each other in a two-person group. With three people, one mutual exclusion already dooms the draw: Alice must give to Carol (Bob is forbidden), which leaves Bob nobody to give to. The general test (Hall's theorem, in matching theory) says a valid assignment exists exactly when every group of givers collectively has enough allowed receivers — but a practical tool doesn't need the theory: exhaustive backtracking either constructs a draw or proves no draw exists, and it runs instantly at party sizes.

A derangement found by backtracking depends on the order candidates are tried — and that order can come from a seeded random number generator. Fix the seed and the same names with the same exclusions always produce the same draw, which lets an organizer re-verify assignments weeks later or restore a lost message. Leave the seed unset and every run is a fresh, unreproducible draw from the same huge space of possibilities — for 10 participants, one of 1,334,961 (before exclusions thin the field).

Try it yourself

The Secret Santa Pairing tool builds a derangement for your list, enforces mutual exclusions for couples and flatmates, and supports a reproducible seed — all in your browser, nothing uploaded. To feel how often a plain shuffle self-draws, try the Randomizer on your name list and count fixed points, or the Random Team Generator when your group needs teams rather than one-to-one gift pairs.