10 names in a hat — odds that no one picks themself?

Question

I have an annual tradition where 10 names are placed in a hat, and those same 10 members randomly select one at a time. If anyone selects their own name, the entire process restarts.

What are the odds that all 10 people select a name that is NOT themself?

Answer 1

Drawing the slips so nobody gets their own is equivalent to putting them in the same order as the people, then rearranging them so none is in its original place. A rearrangement that achieves this is known as a derangement.

Counting derangements is trickier than one would think. A person whose slip has already been drawn can choose freely, while someone whose slip hasn't been drawn can't—and we have to somehow account for both possibilities. It gets quite intricate.

SoI won't try to explain the counting process here. I'll simply say there's a number $!n$ (the subfactorial of $n$) which counts the number of derangements of $n$ items. $!n$ can be calculated either a laborious way, or a ridiculously straightforward way.

Laborious way

The formula is

$$!n=n! \left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-... +\frac{(-1) ^n}{n!} \right)$$

(The $(-1)^n$ is just a way of saying that the plus and minus signs keep alternating.)

Easy way

$$!n≈ \frac{n!}{e}$$

The approximation is so close that for any $n>0$, $!n$ is simply the nearest integer to $\frac{n!}{e}$.

This happens because the bracketed part of the laborious formula also happens to be the first few terms of a series for calculating $\frac{1}{e}$.

Getting the answer

To get the probability of nobody drawing their own name, we need to divide the number of derangements of the slips by the total number of possible arrangements. For $n$ slips:

• the number of possible arrangements is $n!$ (since there are $n$ choices for the first one, $n-1$ for the second, and so on).
• the number of derangements is $!n$.

So the probability $P_n$ of nobody drawing their own slip is $$P_n=\frac{!n}{n!}.$$

We've now got several ways to calculate this for $10$ people:

• divide the nearest integer to $\frac{10!}{e}$ by $10!$.
• notice that $\frac{!n}{n!}$ is just the bracketed part of the laborious formula, and use that.
• be satisfied with an approximation: if $!n≈ \frac{n!}{e}$, then $\frac{!n}{n!} ≈ \frac{1}{e}$.

Just for the fun of it, let's try all three.

Doing it the first way:

$$P_{10} =\frac{1,334,961}{3,268,800}=\frac{16,481}{44,800} ≈0.3679$$

The second way:

$$P_{10} = \frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}...+\frac{1}{10!}≈0.3679$$

The third way:

$$P_{10}≈\frac{1}{e}≈0.3679$$

Although this is an approximation, it's not particularly approximate: it doesn't differ from the correct value until the $8$th decimal place.

So the probability that nobody out of the $10$ draws their own name is about $0.3679=36.79\%$, and is nearly exactly $\frac{1}{e}$.