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

Question

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

Answer 1

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