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.
 A: 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.
A: 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.
A: Hint: ${{n} \choose {i}} \cdot!(n-i)$ counts the number of permutations that fix exactly $i$ elements.
A: 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.
