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!

Consider sequences of length $n+1$ using letters from an alphabet of size $n$.
Both sides count the number of such sequences in which one letter appears twice, and all other letters appear exactly once.
Right-hand side:

 There are $n$ ways to choose the letter that appears twice. There are $(n+1)!$ ways to order the $n+1$ letters if they were distinct; we divide by $2$ to account for the letter that appears twice.

Left-hand side: note that any sequence of length $n+1$ that does not satisfy the above property must not contain all $n$ letters of the alphabet.

 Let $A_j$ be the set of such sequences that are missing the letter $j$. Then by inclusion exclusion, the set of sequences that are missing at least one letter of the alphabet is $\left|\bigcup_{j=1}^n A_j\right| = -\sum_{k=1}^n \binom{n}{k} \left|\bigcap_{j=1}^k A_j\right| (-1)^k = - \sum_{k=1}^n \binom{n}{k} (n-k)^{n+1} (-1)^k$. Subtracting this from the total number of sequences $n^{n+1}$ gives $\sum_{k=0}^n \binom{n}{k} (n-k)^{n+1} (-1)^k$.

