### Still Counting with Integrals

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}$.