Combinatorial Proof of Derangement Identity $n!=\sum_{i=0}^n \binom{n}{n-i}D_i$

Question

Let $D_n$ be the number of derangements of n objects. Find a combinatorial proof of the following identity:

$n! = D_n + \dbinom{n}{1} \cdot D_{n-1}+ \dbinom{n}{2} \cdot D_{n-2} + \cdots + \dbinom{n}{n-1} \cdot D_1 + \dbinom{n}{n} \cdot D_{0}$

This question has been somewhat asked and answered before here Finding a combinatorial proof of this identity: $n!=\sum_{i=0}^n \binom{n}{n-i}D_i$

However, I need to come up with a combinatorial proof. I don't think the answer provided in the linked page is a combinatorial proof. When I learned about combinatorial proofs I was told they need to be more 'real life.' For example, in a committee of $n$ people, a subcommittee and a president must be chosen...

How can I write a true combinatorial proof for this identity?

Answer 1

All permutations of $N$ objects have between $0$ and $N$ objects in their original position. Then count each case, and add them all up:

• Pick zero objects to keep in their original position. Scramble the remaining $N$ objects.
• Pick one object to keep in its original position. Scramble the remaining $N-1$ objects.
• Pick two objects to keep in their original positions. Scramble the remaining $N-2$ objects.
• ($N-4$ similar statements ...)
• Pick $N-1$ objects to keep in their original position. Scramble the remaining $1$ object.
• Pick $N$ objects to keep in their original positions. Scramble the remaining $0$ objects.

All of these cases have the same form: "Pick $n$ objects out of $N$" has $_NC_n$ choices. "Scramble $m$ objects" has $D_m$ choices.