Hints on the right-hand side of a combinatorial proof question

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!

Answer 1

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$.

Answer 2

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.