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 , 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
with initial conditions
It is convenient to rewrite the recurrence as
To begin, let’s solve the recurrence with the initial conditions .
Continuing the pattern, we find that for .
If we multiply by and integrate, then the same recurrence will hold, so we conclude that
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.
In this formula, is the number of times that the ith letter appears, and is a Laguerre polynomial. Specializing this formula to the case
gives a formula for the number of derangements of n objects.
I was struck by the similarity between the integral formulas for and , and this led me to discover a similar formula for .