How to prove $\sum\limits_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$? How do I prove the following identity directly?
$$\sum_{k=0}^n{n \choose k}(k-1)^k(n-k+1)^{n-k-1}= n^n$$
I thought about using the binomial theorem for $(x+a)^n$, but got stuck, because I realized that my $x$ and $a$ in this case are dynamic variables. Any hints? Don't give me the answer; I really want to think through this on my own, but a nudge in the correct direction would be awesome. Thanks! 

As an additional observation I would like to point out that the series expansion of $$e^{\alpha T(z)}$$ where $$T(z) = z \times e^{T(z)}$$ can also be computed with the Cauchy Residue Theorem, which gives a variant of Lagrange Inversion.
We seek to compute $$[z^n] e^{\alpha T(z)} =
\frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} e^{\alpha T(z)} \; dz.$$
Put $w=T(z)$ in the functional equation for $T(z)$ to get 
$$z = w e^{-w} \quad \text{and} \quad
dz = e^{-w} - w e^{-w} = (1-w) e^{-w}.$$
Substitute this into the integral to obtain
$$\frac{1}{2\pi i} \int_{|w|=\epsilon} 
\frac{e^{w(n+1)}}{w^{n+1}} e^{\alpha w} e^{-w} (1-w) \; dw.$$
This is
$$\frac{1}{2\pi i} \int_{|w|=\epsilon} 
\frac{e^{w(n+\alpha)}}{w^{n+1}} (1-w) \; dw.$$
Now we can read off the residue at $w=0$ to get
$$\frac{(n+\alpha)^n}{n!} - \frac{(n+\alpha)^{n-1}}{(n-1)!}
= (n+\alpha) \frac{(n+\alpha)^{n-1}}{n!} - n \frac{(n+\alpha)^{n-1}}{n!}
= \alpha  \frac{(n+\alpha)^{n-1}}{n!}$$
as quoted in the answer by @vonbrand above.
