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}} \quad!(n-i)$$

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.

-
Please do not post the proof if you know it, just ideas are what I am seeking. –  picakhu Dec 16 '10 at 4:27

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

-
Thanks, I will see if that helps. –  picakhu Dec 16 '10 at 4:31
Yup, it helps. I believe I have what I need for the proof –  picakhu Dec 16 '10 at 4:33

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.

-
Thanks, but I am not looking for a proof –  picakhu Dec 16 '10 at 4:31
Nice article! Thanks for sharing, Mike. –  Guess who it is. Dec 16 '10 at 4:55

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.

-
This looks awesome. Well, both the solution and the "spoilering" method. Maybe we should all be doing it for complete solutions... –  Guess who it is. Dec 16 '10 at 5:55
See this on meta.SO for how to implement this, meta.stackexchange.com/questions/1191/…, and this question on meta, meta.math.stackexchange.com/questions/1349/re-spoiler-space. Thanks to Douglas Stones for thinking of this and Jonas Meyer for finding out how! –  Mike Spivey Dec 16 '10 at 6:00

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.

-