In an earlier post we defined the deranged postman problem. Postman Pat is trying to deliver items of mail to different addresses, but having broken his glasses he simply posts one item at random through each letterbox. What is the probability that no letter gets delivered to the right address? Remarkably, it turns out that as , the probability . 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 has two derangements: and . The arrangement , for example, is not a derangement because it leaves element in place. The number of derangements of a set with elements is , the subfactorial of . Using this notation, the probability that a “randomly chosen” perturbation is a derangement is
since there are possible permutations of a set of elements (which is where the definition of comes from).
We can calculate recursively. For , we have , because there is no way to reorder that doesn’t leave the element in the same place. For , we have , because we can derange in precisely one way, . For , we have the recurrence relation
Where does this come from? Like most combinatorical results, it’s just a matter of counting.
Assume that we have letterboxes and letters. Suppose that letterbox receives letter . (There are ways this can happen, i.e. possible choices of .) There are now two possibilities.
- If letterbox now receives letter , the set has been deranged within itself; the remaining letters must also be deranged independently of what happens to letters and , so we have ways this can happen.
- If letterbox does not receive letter , we need to count the number of ways that the remaining letters can be ordered so that letter doesn’t end up in the th letterbox for all , and letter doesn’t end up in letterbox . But this is exactly equivalent to deranging a set of letters, so the number of ways it can happen is .
Putting these together, we obtain the recurrence relation (*).
In fact, we can write a closed formula for ,
To prove that this is correct, use induction starting with the results for and … this is left as an exercise for the reader!
Now we’re nearly there. We have
and so as we have
recognising the usual power series expansion for .
In fact, the power series converges so rapidly that the large- limit is a pretty good approximation even when isn’t very large. For , for example, , while by , the error is less than .
So there we are: from a discrete problem, we’ve found our way to the quantity which we usually think of as arising mainly in calculus. I think this is a lovely illustration of the way that familiar quantities like and can turn up unexpectedly in maths problems. If you don’t see why it’s lovely, maybe you should have gone to Specsavers too…