December | 2011 | Random Math

I have decided to switch the focus of this blog. Instead of expository write-ups, I will be posting mostly tidbits of fun mathematics, possibly without relation to one another.

In this post, I want to talk about the problem of derangements, fist considered by Niclaus Bernoulli (1687-1759), solved by him and, later, independently by Euler. If I write letters to ${100}$ different friends, and send the letters randomly among them, what is the probability that none of my friends will receive the letter personally addressed to them? Since there are ${100!}$ different ways of sending the letters, this probability equals ${!100/100!}$ , where ${!100}$ denotes the number of ways of rearranging ${100}$ objects in such a way that no object is left in the same position. Such a permutation is called a derangement.

How can we calculate ${!100}$ ? First, note that any permutation of ${n}$ objects fixes certain elements, and deranges the others. The number of permutations of ${n}$ fixing exactly ${k}$ elements is equal to

$\displaystyle {n \choose k} !(n-k).$

Therefore, the total number of permutations is

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

In the language of species, we can say that the species of permutations is the product of the species of derangements and of the identity species.

In the language of generating functions, this translates to

$\displaystyle \frac{1}{1-x} = e^x D(x)$

where ${D(x)= \sum_{n=0}^\infty !n \frac{x^n}{n!}}$ .

Therefore,

$\displaystyle D(x)=\frac{e^{-x}}{1-x}$

and from this we read off the formula

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

In fact, rearranging this shows that

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

which is simply the truncated Taylor series for ${e^{-x}}$ , evaluated at ${1}$ . Hence we see that

$\displaystyle \frac{!n}{n!} - e^{-1} \rightarrow 0.$

But even more is true: using Taylor’s remainder formula, we see that for all ${n>0}$ ,

$\displaystyle \left |\frac{!n}{n!} - e^{-1} \right | < \frac{1}{(n+1)!}.$

Hence, in fact, ${!n}$ is the nearest integer to ${n!/e}$ , for all ${n}$ .

Furthermore, as a consequence of the identity ${\frac{1}{1-x} = 1+\frac{x}{1-x}}$ , we see that ${!n}$ satisfies the recurrence relation

$\displaystyle !n = n\times !(n-1) + (-1)^n.$

Note that this is the same recurrence as satisfied by ${n!}$ , with an extra ${(-1)^n}$ term.

The derangement numbers appear in certain integrals. For instance, for ${n\geq 0}$ ,

$\displaystyle \int_1^e (\log u)^n \mathrm{d}u = (-1)^n(e!n-n!).$

This gives another proof that ${!n - n!e^{-1} \rightarrow 0}$ (and that it oscillates around ${0}$ ), since clearly the integral is positive and converges to ${0}$ . It also gives a continuation of the function ${!n}$ to complex values.

Random Math

Monthly Archives: December 2011

The Problem of Misaddressed Letters

Follow “Random Math”