Still Counting with Integrals

by David Radcliffe

Mathematical proofs can often seem like magic tricks, because the authors do not explain how they discovered the ideas that led to their solutions. We endeavor to guide the reader along the shortest path from Point A to Point B, but sometimes it is better to take the scenic route.

The great mathematician Carl Gauss was known for writing clever solutions that concealed the original method of solution. His contemporary, Niels Abel, said of Gauss that “He is like the fox, who effaces his tracks in the sand with his tail.”

In my previous post, I pulled a rabbit out of a hat. I solved a recurrence by “guessing” the solution and plugging it in. In this post, I will explain how the solution could be discovered without guessing, and then I will reveal how I actually solved it.

We considered the  quantity a_{n,k}, the number of permutations of n objects that leave none of the first k elements fixed. We showed that this triangular array of numbers satisfies the recurrence

a_{n,k} - a_{n,k+1} = a_{n-1,k}

with initial conditions

\displaystyle a_{n,0} = n! = \int_0^\infty x^n e^{-x}\, dx.

It is convenient to rewrite the recurrence as

a_{n,k} - a_{n-1,k} = a_{n,k+1}.

To begin, let’s solve the recurrence with the initial conditions a_{n,0} = x^n.

a_{n,0} - a_{n-1,0} = x^n - x^{n-1} = x^{n-1} (x - 1) = a_{n,1}

a_{n,1} - a_{n-1,1} = x^{n-1}(x - 1) - x^{n-2}(x - 1) = x^{n-2} (x - 1)^2 = a_{n,2}

Continuing the pattern, we find that a_{n,k} = x^{n-k} (x - 1)^k for 0 \le k \le n.

If we multiply by e^{-x} and integrate, then the same recurrence will hold, so we conclude that

\displaystyle a_{n,k} = \int_0^\infty x^{n-k} (x - 1)^k e^{-x}\, dx.

So is this how I discovered the formula? Not quite. To gain insight into the problem, I read the Wikipedia article on derangements. This article contains a complicated formula for the number of derangements of a word with repeated letters.

\displaystyle \int_0^\infty P_{n_1}(x) P_{n_2}(x) \cdots P_{n_r}(x) e^{-x}\, dx.

In this formula, n_i is the number of times that the ith letter appears, and P_n is a Laguerre polynomial. Specializing this formula to the case

n_1 = n_2 = \ldots = n_r = 1

gives a formula for the number of derangements of n objects.

\displaystyle D(n) = \int_0^\infty (x-1)^n e^{-x}\, dx.

I was struck by the similarity between the integral formulas for D(n) and n!, and this led me to discover a similar formula for a_{n,k}.

Advertisements