Proving a combinatorial summation equality The following equalities appear to hold for all $n \geq 0 $. How can we prove them?
$$ \sum_{k=0}^{n} \frac{n!}{k!} n^k $$
$$ = \sum_{k=0}^{n} \binom{n}{k} k^k (n-k)^{n-k} $$
$$ = \sum_{k=0}^{n} \binom{n}{k} (n+k)^k (-k)^{n-k} $$
 A: We prove that $(1) = (2).$ Seeking to simplify
$$\bbox[5px,border:2px solid #00A000]{
S_n = \sum_{k=0}^n {n\choose k} k^k (n-k)^{n-k}}$$
where  $n\ge 1$  we recall  the tree  function $T(z)$  with functional
equation
$$T(z) = z \exp T(z)$$
which by Cayley's theorem is
$$T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$
The functional equation arises from  the combinatorial class of rooted
labeled trees:
$$\def\textsc#1{\dosc#1\csod}
\def\dosc#1#2\csod{{\rm #1{\small #2}}}
\mathcal{T} = \mathcal{Z} 
\times \textsc{SET}(\mathcal{T}).$$
Now we have
$$z T'(z) = \sum_{n\ge 1} n^n \frac{z^n}{n!}$$
so that with $n\ge 1$ 
$$S_n = n! [z^n] (1 + z T'(z))^2
= n! [z^n] 2 z T'(z) + n! [z^n] z^2 T'(z)^2
\\ = 2 n! [z^{n-1}] T'(z)  + n! [z^n] z^2 T'(z)^2
= 2 n^n + n! [z^{n-2}] T'(z)^2.$$
We also have from the functional equation
$$T'(z) = \frac{1}{z} T(z) + T(z) T'(z)$$
so that
$$T'(z) = \frac{1}{z} \frac{T(z)}{1-T(z)}.$$
This yields
$$S_n = 2n^n +  n! [z^{n-2}] 
\frac{1}{z} \frac{T(z)}{1-T(z)} T'(z)
\\ = 2n^n + n! [z^{n-1}] 
\frac{T(z)}{1-T(z)} T'(z).$$
Now  we have  for the  remaining coefficient  extractor by  the Cauchy
Coefficient Formula:
$$n! [z^{n-1}] \frac{T(z)}{1-T(z)} T'(z)
= \frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^n} \frac{T(z)}{1-T(z)} T'(z) \; dz.$$
Putting $T(z) = w$ so that $T'(z) \; dz = dw$ and $z = w \exp(-w)$
we find
$$\frac{n!}{2\pi i}
\int_{|w|=\gamma} \frac{\exp(nw)}{w^n} \frac{w}{1-w} \; dw
\\ = \frac{n!}{2\pi i}
\int_{|w|=\gamma} \frac{\exp(nw)}{w^{n-1}} \frac{1}{1-w} \; dw.$$
This is
$$n! \sum_{k=0}^{n-2} [w^k] \exp(nw) [w^{n-2-k}] \frac{1}{1-w}
= n! \sum_{k=0}^{n-2} \frac{n^k}{k!}.$$
We thus obtain
$$2n^n + n! \sum_{k=0}^{n-2} \frac{n^k}{k!}.$$
Note however that for $k=n-1$ and $k=n$ we get from the sum
$$n! \frac{n^{n-1}}{(n-1)!} + n! \frac{n^n}{n!}
= 2n^n$$
which means we can merge the two terms to obtain
$$\bbox[5px,border:2px solid #00A000]{
S_n = n! \sum_{k=0}^{n} \frac{n^k}{k!}.}$$
