### Counting with Integrals

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