Will Someone Draw Their Own Name in Secret Santa?

Everyone draws a name from a hat. What's the chance that nobody draws their own? Inclusion–exclusion counts the bad draws, and the answer hardly depends on the size of the group: about 37%, or 1/e.

How it works

Inclusion–exclusion and derangements

In one sentence

A derangement of $\{1, \dots, n\}$ is a permutation with no fixed points. By inclusion–exclusion $D_n = \sum_{k=0}^{n}(-1)^k\binom{n}{k}(n-k)! = n!\sum_{k=0}^{n}\frac{(-1)^k}{k!}$ , so $D_n/n! \to e^{-1}$ ; in fact $D_n$ is the integer nearest $n!/e$ for $n \ge 1$ .

General formula

{\htmlData{sym=0}{D_n}} = {\htmlData{sym=1}{n}}!\sum_{{\htmlData{sym=2}{k}}=0}^{\htmlData{sym=1}{{n}}}\frac{(-1)^{\htmlData{sym=2}{k}}}{{\htmlData{sym=2}{k}}!}, \qquad \frac{{\htmlData{sym=0}{D_n}}}{{\htmlData{sym=1}{n}}!} \to \frac{1}{e}

Start with all draws, subtract those where someone gets themselves, add back what was subtracted twice, and so on: the alternating corrections home in on 1/e.

What the symbols mean

$D_n$
Derangements
Arrangements of n names in which nobody gets their own.
$n$
Group size
How many people are drawing.
$k$
Term index
How many people are forced to draw themselves in each inclusion–exclusion term.

Let $A_i$ be the draws where person $i$ gets their own name. If $j$ particular people draw themselves, the other $n - j$ names can be arranged in $(n - j)!$ ways.
Inclusion–exclusion over the $A_i$ counts the draws where at least one person gets themselves; subtracting from $n!$ leaves the derangements, $D_n = n!\sum_{k=0}^{n} \frac{(-1)^k}{k!}$ .
Dividing by $n!$ gives the chance that nobody draws themselves: $1 - 1 + \frac12 - \frac16 + \cdots$ , the series for $1/e$ .
The terms shrink so fast that from about 5 people on the answer is 0.368 to three decimal places, whatever the group size.

Learn the math

Permutations and CombinationsDiscrete · Lesson 15, Counting Inclusion–ExclusionDiscrete · Lesson 18, Counting