Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

Any hints about how to prove $$!n = n!- \sum_{i=1}^{n} {{n} \choose {i}} \quad!(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.

share|improve this question
    
Please do not post the proof if you know it, just ideas are what I am seeking. –  picakhu Dec 16 '10 at 4:27
add comment

4 Answers

up vote 8 down vote accepted

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

share|improve this answer
    
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
add comment

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.

share|improve this answer
    
Thanks, but I am not looking for a proof –  picakhu Dec 16 '10 at 4:31
1  
Nice article! Thanks for sharing, Mike. –  J. M. Dec 16 '10 at 4:55
add comment

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.

share|improve this answer
2  
This looks awesome. Well, both the solution and the "spoilering" method. Maybe we should all be doing it for complete solutions... –  J. M. Dec 16 '10 at 5:55
2  
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
add comment

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.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.