Two nice integrals for derangements

We know that the gamma function

satisfies

for positive integers . That is, we have

for all .

Now, recall also that the derangements of a list are the permutations for which no element is in its starting position. And is the number of derangements of elements. For example, :

1 2 3 4
-------
2 1 4 3
2 3 4 1
2 4 1 3
3 1 4 2
3 4 1 2
3 4 2 1
4 1 2 3
4 3 1 2
4 3 2 1


It is not hard to show, by the inclusion-exclusion principle, that

So that, for example:

Now, note that

So the derangements formula above can be written as:

Now suppose we express each factorial in terms of the gamma integral, collecting everything together as one integral:

Notice now that the expression in parentheses is just a binomial expansion, so that

This is the first “nice integral” How good is that!

By the change of variables the gamma integral can be rewritten so that

which is an integral first investigated by Euler. And so

This is the second “nice integral”. If you don’t like all the negative signs in the integrand, then you can equivalently write

or

Most computer algebra systems should be able to handle these integrals; they may be improper, but they are also quite well-behaved. I found that Maxima managed very well, as does Python with SymPy.

I was delighted to learn about these. I’d known about the gamma function for a long time, but I’d never even imagined there might be a similar integral for derangements.

Much of this material (up to the first integral, at least), you can also see on Mike Spivey’s excellent blog, here. On this blog, also, is given a reference to an article where this integral is examined in detail: “Integrals don’t have anything to do with discrete math, do they?>” by P. Mark Kayll; happily this article is available here. I’m not sure where the integral representation of derangements first originated, but no doubt not recently.

And of course once you have a new representation, you can do all sorts of things with it. For example, integration by parts produces the standard recurrence

which can be used to produce

And so on…

One thought on “Two nice integrals for derangements”

1. You probably know this but I think it should be pointed out that D_n has a representation as the Incomplete Gamma function.
http://dlmf.nist.gov/8
Which has a lot of known properties; although I haven’t seen the relationship to combinatorics mentioned above.
Ray