How to prove $ \sum_{r=1}^{k-1} \binom{k}{r}\cdot r^r \cdot (k-r)^{k-r-1} = k^k-k^{k-1} $

We can prove this using the labelled tree function that is known from combinatorics. The idea that we use a convolution is sound but we actually have to do the algebra.

This will provide a closed form of the exponential generating function of the two terms that are involved.

We seek to show that $$\sum_{r=1}^{k-1} {k\choose r} r^r (k-r)^{k-r-1} = k^k - k^{k-1}.$$

Observe that when we multiply two exponential generating functions of the sequences $\{a_n\}$ and $\{b_n\}$ we get that

$$ A(z) B(z) = \sum_{n\ge 0} a_n \frac{z^n}{n!} \sum_{n\ge 0} b_n \frac{z^n}{n!} = \sum_{n\ge 0} \sum_{k=0}^n \frac{1}{k!}\frac{1}{(n-k)!} a_k b_{n-k} z^n\\ = \sum_{n\ge 0} \sum_{k=0}^n \frac{n!}{k!(n-k)!} a_k b_{n-k} \frac{z^n}{n!} = \sum_{n\ge 0} \left(\sum_{k=0}^n {n\choose k} a_k b_{n-k}\right)\frac{z^n}{n!}$$

i.e. the product of the two generating functions is the generating function of $$\sum_{k=0}^n {n\choose k} a_k b_{n-k}.$$

In the present case we have $$A(z) = \sum_{q\ge 1} \frac{q^q}{q!} z^q \quad\text{and}\quad B(z) = \sum_{q\ge 1} \frac{q^{q-1}}{q!} z^q.$$

The species of labelled trees has the specification $$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}}\mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T})$$ which gives the functional equation $$T(z) = z \exp T(z).$$

Extracting coefficients via Lagrange inversion we have $$Q_n = n! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z) dz.$$

Put $T(z)=w$ so that $z=w/\exp(w) = w\exp(-w)$ and $dz = \exp(-w) - w\exp(-w) \; dw$ to get $$n! \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(n+1))}{w^{n+1}} \times w\times (\exp(-w) - w\exp(-w)) dw \\ = n! \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(wn)}{w^n} (1 - w) dw.$$

But we have $$n! [w^{n-1}] \exp(w n) = n! \times \frac{n^{n-1}}{(n-1)!} = n^n$$ and $$n! [w^{n-2}] \exp(w n) = n! \times \frac{n^{n-2}}{(n-2)!} = n (n-1) n^{n-2} = (n-1) n^{n-1}$$ which means that $T(z)$ is the exponential generating function of $$n^n - (n-1) n^{n-1} = n^{n-1} \quad\text{i.e.}\quad T(z) = \sum_{q\ge 1} \frac{q^{q-1}}{q!} z^q.$$ This also follows from Cayley's theorem.

The equality that we seek to prove is the convolution the two exponential generating functions $A(z)$ and $B(z)$ and to verify it we must show that $$k! [z^k] A(z) B(z) = k^k - k^{k-1}.$$ But we have (differentiate termwise) $$A(z) = z \frac{d}{dz} T(z) \quad\text{and}\quad B(z) = T(z).$$

Observe that $$z T'(z) = z \left(\exp T(z) + z \exp T(z) T'(z) \right) = T(z) + z T(z) T'(z)$$ which implies that $$z T'(z) = \frac{T(z)}{1-T(z)}.$$

It follows that $$k! [z^k] A(z) B(z) = k! \frac{1}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{k+1}} \frac{T(z)^2}{1-T(z)} dz.$$ Using the same substitution as before this becomes $$k! \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(w(k+1))}{w^{k+1}} \times \frac{w^2}{1-w}\times (\exp(-w) - w\exp(-w)) dw \\ = k! \frac{1}{2\pi i} \int_{|w|=\epsilon} \frac{\exp(wk)}{w^{k-1}} dw = k! \frac{k^{k-2}}{(k-2)!} = (k-1) k^{k-1} = k^k - k^{k-1}.$$

The labelled tree function recently appeared at this MSE link.