# Combinatorial proof of $D_n= nD_{n-1}+(-1)^n$

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.

• Do you mean $D_n= nD_{n-1}+(-1)^n$? – Robert Z Aug 12 '19 at 7:07
• @RobertZ Yes. Thanks for spotting the typo that I corrected. – 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$$.
• 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. – mathcounterexamples.net Aug 12 '19 at 8:10