I’ve only just learned about this!
We know that the gamma function
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
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…