A Nice Proof of the Derangements Formula

A derangement is a permutation in which none of the elements is mapped to itself.  The formula for the number of derangements D_n on n elements is

\displaystyle D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.

This formula is normally proved using inclusion-exclusion (and, in fact, it is one of the classic illustrations of inclusion-exclusion).

A few days ago on math.SE robjohn posted a nice proof of this formula that I had never seen before.  It starts with the recurrence relation D_n = (n-1)(D_{n-1} + D_{n-2}) and initial conditions D_0 = 1, D_1 = 0.  (The recurrence relation can be proved combinatorially; see robjohn’s post or mine on the same question.)  Then, subtract nD_{n-1} from both sides of the recurrence relation to get

\displaystyle D_n - nD_{n-1} = -(D_{n-1} - (n-1)D_{n-2}).

Let A_n = D_n - n D_{n-1}, and the recurrence relation becomes A_n = - A_{n-1}.  With A_0 = 1, this recurrence is easy to solve, and we get D_n - n D_{n-1} = A_n = (-1)^n.

Now, divide both sides of D_n - n D_{n-1} = (-1)^n by n! to obtain

\displaystyle \frac{D_n}{n!} - \frac{D_{n-1}}{(n-1)!} = \frac{(-1)^n}{n!}.

Let B_n = \frac{D_n}{n!}.  Thus we have B_n = B_{n-1} + \frac{(-1)^n}{n!}.  With B_0 = 1 this recurrence is also easy to solve, and we get

\displaystyle \frac{D_n}{n!} = B_n = \sum_{k=0}^n \frac{(-1)^k}{k!}.

Multiplying both sides by n! yields the derangement formula:

\displaystyle D_n = n! \sum_{k=0}^n \frac{(-1)^k}{k!}.

This entry was posted in combinatorics, derangements, permutations, recurrence relations. Bookmark the permalink.

5 Responses to A Nice Proof of the Derangements Formula

  1. Dave Perkins says:

    Thanks for providing extra detail that the original math.SE posts left out. Very lovely proof! If I wanted to use the proof in a paper, do you know how I’d cite it? I can’t find the original author of this proof and wonder if you happen to know it.

    • mzspivey says:

      I haven’t seen the proof in a book or paper before. I think it would be fine to cite the original math.SE post or even mine here using some standard format for citing web pages. You could also ask robjohn on math.SE if he got it from some other source.

  2. John says:

    You wrote that the recurrence is easy to solve. Could you please elaborate on how you arrived at A_n = (-1)^n? Thanks.

Leave a Reply

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

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 )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s