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.

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

  3. William P. G. SHAW says:

    The derangement formula is the very thing I need to make strong passwords by mapping the upper and lower case alphabet, numerals zero to nine [excluding one which is indistiguishable from lower case L and other indistiguishables] and a few non-alphabetic characters such as £*%, about sixty-seven in all to a derangement of the integers from one to sixty-seven.
    In using the recursive formula, the initial cases D[0] and D[1] need to be stated clearly.

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 )

Google+ photo

You are commenting using your Google+ 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 )


Connecting to %s