2
$\begingroup$

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?

$\endgroup$
3
$\begingroup$

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.

$\endgroup$

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.