Using combinatorial reasoning to show $n!=\binom{n}{0}D_n+\binom{n}{1}D_{n-1}+\dots+\binom{n}{n}D_0$

1k Views Asked by At

How can one use combinatorial reasoning to show that

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

Now $D$ stands for deranged which is a permutation when a number is not its "natural position." For example $\{2,3,1\}$ or $\{3,1,2\}$.

The formula for derangement is $$D_m=m!\left(1-\frac{1}{1!}+\frac{1}{2!}-\frac{1}{3!}+\dots+(-1)^m\frac{1}{m!}\right)$$

1

There are 1 best solutions below

5
On BEST ANSWER

Each term ${n \choose k}D_k$ represents choosing $k$ elements to be fixed in a permutation, then making sure none of the other elements is fixed. The sum is over all numbers of elements that can be fixed, so all permutations are accounted for. You can even delete one term as $D_1=0$