Consider a finite set $S_n$ with $n\ge 2$ elements and denote by $D_n$ the number of derangements of $S_n$.

How to prove by a direct combinatorial proof that

$$D_n= nD_{n-1}+(-1)^n ?$$

I know a proof based on Euler equality

$$D_n = (n-1)(D_{n-1} + D_{n-2})$$

and tried to separate the cases $n$ even and odd... but I’m not able to get a clean proof so far.

  • $\begingroup$ Do you mean $D_n= nD_{n-1}+(-1)^n$? $\endgroup$ – Robert Z Aug 12 '19 at 7:07
  • $\begingroup$ @RobertZ Yes. Thanks for spotting the typo that I corrected. $\endgroup$ – mathcounterexamples.net Aug 12 '19 at 7:08

I give you a reference to a nice (and short) paper of A. T. Benjamin and J. Ornstein: A bijective proof of a derangement recurrence. Their bijection is based on the number of elements in the cycle of each permutation which contains the smallest element $1$.

The authors note that Richard Stanley points out in his classic text Enumerative Combinatorics that "considerably more work is required to prove such recurrence combinatorially".

  • $\begingroup$ Thanks Robert to point me to those papers. Interesting to see the way to create an almost correspondence between the set of derangements and the set of permutations with exactly one fixed point. And how the almost covers the term $(-1)^n$ of the equation to be proven. $\endgroup$ – mathcounterexamples.net Aug 12 '19 at 8:10
  • $\begingroup$ I’ll also look at this article which is a reference of the article provided in your answer. $\endgroup$ – mathcounterexamples.net Aug 12 '19 at 8:16
  • $\begingroup$ @mathcounterexamples.net Well done! Thanks, I will look through Remmel's article. $\endgroup$ – Robert Z Aug 12 '19 at 8:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.