Hints on the right-hand side of a combinatorial proof question $\sum_{k=0}^{n}  {n \choose k} (n-k)^{n+1}(-1)^{k} = \frac {n(n+1)!} {2}$
So the left-hand side looks so much like inclusion-exclusion principle. The sign changes between - and + depending on whether k is even or odd (due to $(-1)^{k}$) It's like we are subtracting singles but then recounting doubles but then triples are over-counted so we subtract them etc. But the right-hand side is confusing to me. How does the right hand side have anything to do with the left-hand side? What question could I ask for the right-hand side for it to calculate the same thing as the left-hand side? I realize I could think of it as
${n \choose 1} \frac {(n+1)!} {2!}$ as well, but it hasn't helped me much.
Any help would be appreciated. 
Thank you very much!

Write your identity as $$\frac{1}{n!} \sum_{k=0}^n {n\choose k} (-1)^k (n-k)^{n+1} = {n+1\choose 2}.$$
The LHS is $$\frac{1}{n!} \sum_{k=0}^n {n\choose k} (-1)^{n-k} k^{n+1}
= {n+1\brace n}$$ (Stirling number of the second kind) by definition.
Now observe that when partitioning $[n+1]$ into $n$ sets there must be exactly one set containing two elements which yields $${n+1\choose 2}$$ possibilities.
