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.

\displaystyle a_n = \int_0^\infty x^n e^{-x}\, dx

The reader can check that a_n = 1, and integration by parts yields a_n = na_{n-1} for all n \ge 1. Therefore, a_n = n! for all n \ge 0 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 k=0, and the number of derangements when k=n.

We first observe that

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

This is because the difference a_{n,k} - a_{n,k+1} represents the number of permutations that fix the (k+1)-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 n-1 elements that has no fixed points among the first k elements, and there are a_{n-1,k} such permutations.

Let us define

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

We have already shown that I_{n,0} = a_{n,0} = n!, and it is easy to check that I_{n,k} - I_{n,k+1} = I_{n-1,k} for all 0 \le k \le n. This is the same recurrence that the a_{n,k} satisfy. Therefore, I_{n,k} = a_{n,k} for all 0 \le k \le n, by induction on k.

I conjecture that a_{n,k} \approx e^{-k/n} when k and n are large, but I am having difficulty estimating the integral.

Advertisements