## Another Nice Proof of the Derangements Formula

Strangely enough, a couple of days after I made my last post on a way to prove the derangements formula that I had never seen before, I came across another new (to me) way to prove the derangements formula in an article [1] by P. Mark Kayll in Mathematics Magazine from earlier this year.  It involves an an integral representation for the number of derangements $D_n$ on $n$ elements:

$\displaystyle D_n = \int_0^{\infty} (t-1)^n e^{-t} dt.$

(Kayll gives this as a special case of a more general result that says that the number of permutations with a specified set of fixed points can be represented by $\int_0^{\infty} R_{\tilde{G}}(t) e^{-t} dt$, where $\tilde{G}$ is the complement of $G$ in the complete bipartite graph on $n$ elements, and $R_G(t)$ is the associated rook polynomial for $G$.)

I’m going to prove this by showing that the integral representation satisfies the derangements recurrence $D_n = (n-1)(D_{n-1} + D_{n-2})$.  Let $R_n = \int_0^{\infty} (t-1)^n e^{-t} dt$.

Proving the integral formula for $D_n$:
Integration by parts yields
$\displaystyle R_n = (-1)^n + n R_{n-1} ,$

which gives us a recurrence for $R_n$.  Applying this recurrence again with $R_{n-1}$ yields

$\displaystyle R_n = (-1)^n + (n-1)R_{n-1} + R_{n-1} \\ = (-1)^n + (n-1)R_{n-1} + (-1)^{n-1} + (n-1)R_{n-2} \\ = (n-1)(R_{n-1} + R_{n-2}).\\$

Since $R_0 = 1 = D_0$ and $R_1 = 0 = D_1$, the integral representation is established.

Proving the derangements formula from the integral representation:

We have

$\displaystyle D_n = \int_0^{\infty} (t-1)^n e^{-t} dt \\ = \int_0^{\infty} \sum_{k=0}^n \binom{n}{k} (-1)^k t^{n-k} e^{-t} dt \\ = n! \sum_{k=0}^n \frac{(-1)^k}{k! (n-k)!} \Gamma(n-k+1) \\ n! \sum_{k=0}^n \frac{(-1)^k}{k!}.$

(I added this argument to my answer to “I have a problem understanding the proof of Rencontres numbers.”)

References

1. P. Mark Kayll, “Integrals Don’t Have Anything to Do with Discrete Math, Do They?Mathematics Magazine 84(2): 2011, 108-119.
This entry was posted in combinatorics, derangements, permutations, recurrence relations. Bookmark the permalink.