Another Nice Proof of the Derangements Formula

Posted on November 28, 2011 by

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.
About these ads
This entry was posted in combinatorics, permutations, recurrence relations. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

Gravatar
WordPress.com Logo

You are commenting using your WordPress.com account. ( Log Out / Change )

Twitter picture

You are commenting using your Twitter account. ( Log Out / Change )

Facebook photo

You are commenting using your Facebook account. ( Log Out / Change )

Cancel

Connecting to %s