### 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.

[…] mathblag Just another WordPress.com site Skip to content HomeAbout ← Counting with Integrals […]

Thanks are due to James Tanton for introducing me to this interesting problem.

[…] my previous post, I pulled a rabbit out of a hat. I solved a recurrence by “guessing” the solution and […]