Proof of subfactorial formula $!n = n!- \sum_{i=1}^{n} {{n} \choose {i}} \quad!(n-i)$

Any hints about how to prove $$!n = n!- \sum_{i=1}^{n} {{n} \choose {i}}\,!(n-i)$$

from Wikipedia's article on derangements?

Here, $!n$ is the number of derangements of a set with $n$ elements.

I am not looking for proofs, just nudges in the right direction.

Hint: ${{n} \choose {i}} \cdot!(n-i)$ counts the number of permutations that fix exactly $i$ elements.

I actually prove a generalization of this in my paper "Deranged Exams" (College Mathematics Journal, 41 (3): 197-202, 2010). See Theorem 7.

The generalization is the following. Let $S_{n,k}$ be the number of permutations on $n$ elements in which none of the first $k$ elements remains in its original position. Thus $S_{n,0} = n!$, and the number of derangements on $n$ elements, $D_n$, is $S_{n,n}$.

$$S_{n+k,k} = \sum_{j=0}^n \binom{n}{j} D_{k+j}.$$

The OP's question is the case $k = 0$.

I'll extract the essence of the proof and post it in the next few minutes. Since you want hints rather than a full proof, I'll just leave this as a reference in case you (or anyone else reading this) is interested. Jonas Meyer's answer gives a good hint.

Here's a proof, obscured using spoiler space.

If $d_n$ is the number of derangements on $n$ elements, then the number of permutations on $n$ elements with exactly $i$ fixed points is ${n \choose i} d_{n-i}$ (choose i points to fix, then any permutation that fixes exactly those $i$ points (and nothing else) determines a derangement on the non-fixed points, and there are $d_{n-i}$ such derangements). Hence, $n!=\sum_{i=0}^n {n \choose i} d_{n-i}$, which can be rearranged to give the above formula.

PS. I'm not a fan of the $!n$ notation, I'm pretty sure it's not standard in combinatorics.

The number of derangements is the number of permutations less the number that leave some numbers fixed. So for example the term i=5 in the sum is all the ways to pick 5 out of n to leave fixed and derange all the rest. Then sum over all the numbers of ones that can be fixed.