The deranged postman problem 2

In an earlier post we defined the deranged postman problem. Postman Pat is trying to deliver $n$ items of mail to $n$ different addresses, but having broken his glasses he simply posts one item at random through each letterbox. What is the probability $p(n)$ that no letter gets delivered to the right address? Remarkably, it turns out that as $n \to \infty$, the probability $p(n) \to 1/e$. Let’s see why…

First we define the concept of a derangement. To borrow the excellent description from John D. Cook’s blog, a derangement is a permutation of a set that leaves no element where it started. For example, the set $\{1, 2, 3\}$ has two derangements: $\{2, 3, 1\}$ and $\{3, 1, 2\}$. The arrangement $\{2, 1, 3\}$, for example, is not a derangement because it leaves element $3$ in place. The number of derangements of a set with $n$ elements is $!n$, the subfactorial of $n$. Using this notation, the probability that a “randomly chosen” perturbation is a derangement is

$p(n) = \displaystyle\frac{!n}{n!},$

since there are $n!$ possible permutations of a set of $n$ elements (which is where the definition of $n!$ comes from).

We can calculate $!n$ recursively. For $n = 1$, we have $!n = 0$, because there is no way to reorder $\{ 1 \}$ that doesn’t leave the element $1$ in the same place. For $n = 2$, we have $!n = 1$, because we can derange $\{1, 2\}$ in precisely one way, $\{2, 1\}$. For $n > 2$, we have the recurrence relation

$!(n+1) = n(!n + !(n-1)). \qquad (*)$

Where does this come from? Like most combinatorical results, it’s just a matter of counting.

Assume that we have $(n+1)$ letterboxes and $(n+1)$ letters. Suppose that letterbox $1$ receives letter $i \neq 1$. (There are $n$ ways this can happen, i.e. $n$ possible choices of $i$.) There are now two possibilities.

• If letterbox $i$ now receives letter $1$, the set $\{1, i\}$ has been deranged within itself; the remaining $(n-1)$ letters must also be deranged independently of what happens to letters $1$ and $i$, so we have $!(n-1)$ ways this can happen.
• If letterbox $i$ does not receive letter $1$, we need to count the number of ways that the $n$ remaining letters can be ordered so that letter $j$ doesn’t end up in the $j$th letterbox for all $j \neq i$, and letter $1$ doesn’t end up in letterbox $i$. But this is exactly equivalent to deranging a set of $n$ letters, so the number of ways it can happen is $!n$.

Putting these together, we obtain the recurrence relation (*).

In fact, we can write a closed formula for $!n$,

$!n = n!\displaystyle\sum_{k=0}^n\displaystyle\frac{(-1)^k}{k!}$.

To prove that this is correct, use induction starting with the results for $n = 1$ and $n = 2$… this is left as an exercise for the reader!

Now we’re nearly there. We have

$p(n) = \displaystyle\frac{!n}{n!} = \displaystyle\sum_{k=0}^n\displaystyle\frac{(-1)^k}{k!}$

and so as $n \to \infty$ we have

$\lim_{n\to\infty}p(n) = \displaystyle\sum_{k=0}^{\infty}\displaystyle\frac{(-1)^k}{k!} = \exp(-1) = \displaystyle\frac{1}{e} \approx 0.3678794412,$

recognising the usual power series expansion for $\exp(x)$.

In fact, the power series converges so rapidly that the large-$n$ limit is a pretty good approximation even when $n$ isn’t very large. For $n = 6$, for example, $p(n)-1/e \approx 0.0001761144$, while by $n = 10$, the error is less than $10^{-7}$.

So there we are: from a discrete problem, we’ve found our way to the quantity $e$ which we usually think of as arising mainly in calculus. I think this is a lovely illustration of the way that familiar quantities like $\pi$ and $e$ can turn up unexpectedly in maths problems. If you don’t see why it’s lovely, maybe you should have gone to Specsavers too…

(DP)