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 jth 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)

Advertisements
This entry was posted in Articles. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s