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 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 different ways of sending the letters, this probability equals , where denotes the number of ways of rearranging 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 ? First, note that any permutation of objects fixes certain elements, and deranges the others. The number of permutations of fixing exactly elements is equal to

Therefore, the total number of permutations is

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

where .

Therefore,

and from this we read off the formula

In fact, rearranging this shows that

which is simply the truncated Taylor series for , evaluated at . Hence we see that

But even more is true: using Taylor’s remainder formula, we see that for all ,

Hence, in fact, is the nearest integer to , for all .

Furthermore, as a consequence of the identity , we see that satisfies the recurrence relation

Note that this is the same recurrence as satisfied by , with an extra term.

The derangement numbers appear in certain integrals. For instance, for ,

This gives another proof that (and that it oscillates around ), since clearly the integral is positive and converges to . It also gives a continuation of the function to complex values.

### Like this:

Like Loading...

*Related*

I sometimes look at your blog.

I am blessed! ^_^