Counting with Integrals
by David Radcliffe
Integrals are not usually associated with counting, but there are many interesting quantities that can be counted using integrals. A fundamental example is the number of permutations of a set of n elements.
The reader can check that , and integration by parts yields for all . Therefore, for all by induction.
Let us consider a more general problem. What is the number of permutations of n elements that have no fixed points among the first k elements? This is the number of permutations of n objects when , and the number of derangements when .
We first observe that
This is because the difference represents the number of permutations that fix the -st element but do not fix any of the first k elements. If we delete that fixed element, then we are left with a permutation of elements that has no fixed points among the first k elements, and there are such permutations.
Let us define
We have already shown that , and it is easy to check that for all . This is the same recurrence that the satisfy. Therefore, for all , by induction on k.
I conjecture that when k and n are large, but I am having difficulty estimating the integral.