Links forward

Derangements and \(e\)

Suppose that a group of friends play a gift-giving game for the festive season. Let the number of friends be \(n\). Each person writes their name down, and the names go into a hat. Each person in turn then takes a name out of the hat, until everyone has taken a name out and the hat is empty. You give a gift to the person whose name you pull out of the hat.

Of course, it won't do to give a gift to yourself, so we hope nobody pulls out their own name! What are the chances of this happening?

Obviously, the answer might depend on \(n\). As it turns out, as \(n\) becomes large, the answer approaches \(\dfrac{1}{e}\).

This question can be expressed as a problem about permutations. Number the people in the group from 1 to \(n\). The function assigning each person to the person whose name they pull out of the hat is a one-to-one function

\[ f \colon \{1, 2, \dotsc, n \} \to \{1, 2, \dotsc, n\}, \] also known as a permutation. If person \(i\) pulls their own name out of the hat, then \(f(i) = i\), and \(i\) is said to be a fixed point of the permutation.

A good permutation for the purposes of gift-giving is one with no fixed points. A permutation with no fixed points is called a derangement. Our question is really asking what fraction of permutations are derangements.

The number of permutations of the \(n\) friends is not difficult to calculate. The first person can pick \(n\) possible names out of the hat, the second person \(n-1\) names, and so on. The number of permutations is \(n!\).

We can count the number of derangements \(D_n\) as follows, using a technique known as the principle of inclusion–exclusion.

Starting from all \(n!\) permutations, we exclude those which have a fixed point. There are \(n\) possible people who could be a fixed point, and once there is a fixed point, the remaining \(n-1\) people can be permuted in \((n-1)!\) ways. So we subtract \(n \cdot (n-1)!\).

But, in excluding those permutations, we have excluded some permutations more than once. Permutations with two fixed points will have been subtracted twice. So, for each pair of people, we add back on the number of permutations which have them both as fixed points. There are \(\dbinom{n}{2}\) pairs of people, and the remaining \(n-2\) people can be permuted in \((n-2)!\) ways. So we add back on \(\smash{\dbinom{n}{2} (n-2)!}\).

However, now permutations with three fixed points will have been added back on too many times, and have been counted when they shouldn't be. So, for every group of three people, we subtract the number of permutations which have them all as fixed points. There are \(\dbinom{n}{3}\) triples of people, and the remaining \(n-3\) people can be permuted in \((n-3)!\) ways, so we subtract off \(\smash{\dbinom{n}{3} (n-3)!}\).

Continuing in this way, we find that the number of derangements of the \(n\) people is

\[ D_n = n! - \dbinom{n}{1} (n-1)! + \dbinom{n}{2} (n-2)! - \dbinom{n}{3} (n-3)! + \dbinom{n}{4} (n-4)! - \dotsb + (-1)^n \dbinom{n}{n} 0!. \] (The sign of the last term depends on \(n\), and following the usual convention we set \(0! = 1\).) Using the formula \(\dbinom{n}{k} = \dfrac{n!}{k!(n-k)!}\), we can simplify this expression to \[ D_n = n! - \dfrac{n!}{1!} + \dfrac{n!}{2!} - \dfrac{n!}{3!} + \dfrac{n!}{4!} - \dotsb + (-1)^n \dfrac{n!}{n!}. \]

Therefore, the fraction of permutations which are derangements is

\[ \dfrac{D_n}{n!} = 1 - \dfrac{1}{1!} + \dfrac{1}{2!} - \dfrac{1}{3!} + \dfrac{1}{4!} - \dotsb + (-1)^n \dfrac{1}{n!}. \]

If we remember the formula for \(e^x\),

\[ e^x = 1 + \dfrac{x}{1!} + \dfrac{x^2}{2!} + \dfrac{x^3}{3!} + \dotsb + \dfrac{x^n}{n!} + \dotsb, \] then we see that, as \(n \to \infty\), \[ \dfrac{D_n}{n!} \to e^{-1} = \dfrac{1}{e}. \]

So, with a large enough group of friends, the probability of good gift-giving is \(\dfrac{1}{e}\).

Next page - Links forward - Striking it lucky with e