Show that if n is a positive integer, then $$n! = {{n}\choose{0}}d_n + {{n}\choose{1}}d_{n-1} + {{n}\choose{2}}d_{n-2}+\cdots+ {{n}\choose{n-1}}d_1 + {{n}\choose{n}}d_0 $$
where $d_n$ is the number of derangements of $n$ objects.
- We had a general overview lecture of the Inclusion-Exclusion principle and how it relates to the addition principle as well as did several permutation-based problems involving permutations of certain sizes and finding how many total permutations fit a given criteria, although I do not see how that would help me with this proof. Any help is appreciated.
Say we have $n$ different objects and we want to consider in how many ways we can order them in a row (how many ways we can permutate them). On one hand, that is $n!$
On the other hand, say we have originally $n$ objects in $n$ different labeled boxes. We can consider different cases of permutations: when the permutation leaves $0$ objects in its original place, when the permutation leaves exactly $1$ object in its original place, and so on, all the way to the case where the permutation leaves exactly $n$ objects in its original place (that is, we made no change at all.)
Say we consider the $k$-th case. Then we must count the number of ways we can leave exactly $k$ objects fixed. There are ${n\choose k}$ ways to pick $k$ objects out of $n$, and when those $k$ are chosen, we have $d_{n-k}$ ways to derange the rest. That is (as noted by Dylan in comments) ${n\choose k}d_{n-k}$ ways we can leave exactly $k$ objects fixed.
Adding all the cases $k=0,1,\ldots, n$, we have the number of total permutations of $n$ objects. But that number is $n!$. Hence the equality follows:
$$n! = \sum_{k=0}^n{n\choose k}d_{n-k}$$