Two nice integrals for derangements

I’ve only just learned about this!

We know that the gamma function

    \[ \Gamma(x) = \int^\infty_0e^{-s}s^x\,ds \]

satisfies

    \[ \Gamma(n+1) = n! \]

for positive integers n. That is, we have

    \[ n!=\int^\infty_0e^{-x}x^n\,dx \]

for all n\in \mathbb{Z}.

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

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

    \[ D_n=n!\left(\frac{1}{0!}-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\ldots+(-1)^n\frac{1}{n!}\right). \]

So that, for example:

    \begin{align*} D_4&=24\left(\frac{1}{1}-\frac{1}{1}+\frac{1}{2}-\frac{1}{6}+\frac{1}{24}\right)\\ &=24-24+12-4+1\\ &=9. \end{align*}

Now, note that

    \[ \frac{n!}{k!}=(n-k)!{n\choose k}. \]

So the derangements formula above can be written as:

    \[ D_n=n!{n\choose 0}-(n-1)!{n\choose 1}+(n-2)!{n\choose 2}-(n-3)!{n\choose 3}+\ldots+(-1)^n0!{n\choose n}. \]

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

    \[ D_n=\int^\infty_0e^{-x}\left({n\choose 0}x^n-{n\choose 1}x^{n-1}+{n\choose 2}x^{n-2}-{n\choose 3}x^{n-3}+\ldots+(-1)^n{n\choose n}\right)\,dx. \]

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

    \[ D_n=\int^\infty_0e^{-x}(x-1)^n\,dx. \]

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

By the change of variables x=-\ln u the gamma integral can be rewritten so that

    \[ n!=\int^1_0(-\ln u)^n\,du \]

which is an integral first investigated by Euler. And so

    \[ D_n=\int^1_0(-1-\ln u)^n\,du. \]

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

    \[ D_n=(-1)^n\int^1_0(1+\ln u)^n\,du \]

or

    \[ D_n=\left\vert\int^1_0(1+\ln u)^n\,du\right\vert. \]

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

    \[ D_n=nD_{n-1}+(-1)^n \]

which can be used to produce

    \[ D_n=(n-1)(D_{n-1}+D_{n-2}). \]

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
    BTW: Your login via WordPress didn’t really work for me.

Leave a Reply

Your email address will not be published. Required fields are marked *