Prove that $\sum _{k=1}^{n-1} \binom{n-1}{k} k^{k-1} (n-k)^{n-k-1}=n^{n-1}-n^{n-2}$

The combinatorial proof in terms of terms of labelled trees ...

Recall Cayley's result: There are $n^{n-2}$ labelled trees. Now we could choose any of the $n$ verticies to be a root, so there are $n^{n-1}$ rooted labelled trees. We could also choose an edge to be a root, there are $n-1$ edges and the RHS of your formula is precisely these objects.

To obtain the LHS: Delete the edge, this will break the tree into $2$ smaller trees and label the vertices that we attached to the deleted edge to be the root for each of these new trees. One of these trees will have the label $1$ and let $n-k$ be the number of vertices, the other tree will have $k$ vertices. The rest of the labels can be distributed in $ \binom{n-1}{k}$ ways. Thus \begin{eqnarray*} \sum _{k=1}^{n-1} \binom{n-1}{k} k^{k-1} (n-k)^{n-k-1}=n^{n-1}-n^{n-2}. \end{eqnarray*} In a nut shell: This formula represents the number of edge rooted labelled trees, graded by the number of vertices in the two (vertex) rooted trees obtained by deleting the rooting edge.

Recall Cayley's theorem that there are $n^{n-1}$ rooted labeled trees. Introduce

$$ T(z) = \sum_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$

Note also that for the corresponding combinatorial class $\mathcal{T}$ we have that

$$\def\textsc#1{\dosc#1\csod} \def\dosc#1#2\csod{{\rm #1{\small #2}}} \mathcal{T} = \mathcal{Z} \times \textsc{SET}(\mathcal{T}).$$

This gives the functional equation

$$T(z) = z \exp T(z).$$

The first term in the sum convolution is $T(z)$ and the second one

$$T'(z) = \sum_{n\ge 0} (n+1)^n \frac{z^n}{n!}.$$

We thus require

$$(n-1)! [z^{n-1}] T(z) T'(z)$$

By the Cauchy Coefficient Formula this is

$$\frac{(n-1)!}{2\pi i} \int_{|z|=\epsilon} \frac{1}{z^{n}} T(z) T'(z) \; dz.$$

Now put $T(z) = w$ so that $z = w \exp(-w)$ to get

$$\frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{\exp(wn)}{w^{n}} w \; dw = \frac{(n-1)!}{2\pi i} \int_{|w|=\gamma} \frac{\exp(wn)}{w^{n-1}} \; dw.$$

This is

$$(n-1)! \frac{n^{n-2}}{(n-2)!} = (n-1) n^{n-2} = n^{n-1} - n^{n-2}$$

as claimed.

Note that

$$\frac{n^{n-1}}{n!} \sim \exp(n) \frac{1}{\sqrt{2\pi} \times n^{3/2}}$$

so that $T(z)$ converges in a neighborhood of the origin (radius is $1/e.$)

Remark. When building the convolution of EGFs $T(z) T'(z)$ we have used the fact 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!}$$

An algebraic proof somewhat similar in spirit to the nice answer of @MarkoRiedel. Considering the binomial identity $\binom{n}{k}=\binom{n-1}{k}\frac{n}{n-k}$ we multiply OPs identity with $n$ and show the following is valid:

\begin{align*} \sum_{k=1}^{n-1}\binom{n}{k}k^{k-1}(n-k)^{n-k}=n^n-n^{n-1}\qquad\qquad n\geq 2\tag{1} \end{align*}

We use an exponential generating function approach to show (1). The right hand side of (1) indicates as starting point: \begin{align*} A(z)=\sum_{n=1}^\infty n^{n-1}\frac{z^n}{n!}\qquad\qquad A^{\prime}(z)=\sum_{n=1}^\infty n^n\frac{z^{n-1}}{n!}\tag{2} \end{align*}

A generating function of the right-hand side of (1) is according to (2) \begin{align*} zA^{\prime}(z)-A(z)&=\sum_{n=1}^\infty n^n\frac{z^n}{n!}-\sum_{n=1}^\infty n^{n-1}\frac{z^n}{n!}\\ &=\sum_{n=1}^\infty \left(\color{blue}{n^n-n^{n-1}}\right)\frac{z^n}{n!}\tag{3} \end{align*}

The left-hand side of (1) is the coefficient of a convolution of two exponential generating functions. We obtain \begin{align*} A(z)\cdot zA^{\prime}(z)&=\left(\sum_{k=1}^\infty k^{k-1}\frac{z^k}{k!}\right)\left(\sum_{l=1}^\infty l^l\frac{z^l}{l!}\right)\\ &=\sum_{n=2}^\infty \left(\sum_{{k+l=n}\atop{k,l\geq 1}}\frac{k^{k-1}}{k!}\,\frac{l^l}{l!}\right)z^n\\ &=\sum_{n=2}^\infty \left(\sum_{k=1}^{n-1}\frac{k^{k-1}}{k!}\,\frac{(n-k)^{n-k}}{(n-k)!}\right)z^n\\ &=\sum_{n=2}^\infty \left(\color{blue}{\sum_{k=1}^{n-1}\binom{n}{k}k^{k-1}\,(n-k)^{n-k}}\right)\frac{z^n}{n!}\tag{4}\\ \end{align*}

We want to show the equality of (3) and (4) i.e. the validity of the functional equation \begin{align*} zA^{\prime}(z)-A(z)=A(z)\cdot zA^{\prime}(z)\tag{5} \end{align*}

We recall the series representation of the Lambert W-function $W(-z)=-\sum_{n=1}^\infty n^{n-1}\frac{z^n}{n!}$. The functional equation $z=W(z)e^{W(z)}$ indicates the approach

\begin{align*} A(z)=ze^{A(z)}\tag{6} \end{align*}

We obtain \begin{align*} \color{blue}{zA^{\prime}(z)-A(z)}&=z\left(ze^{A(z)}\right)^{\prime}(z)-A(z)\tag{*}\\ &=z\left(e^{A(z)}+zA^{\prime}(z)e^{A(z)}\right)-A(z)\\ &=ze^{A(z)}+z^2A^{\prime}(z)e^{A(z)}-A(z)\\ &=A(z)+zA^{\prime}(z)A(z)-A(z)\tag{*}\\ &\,\,\color{blue}{=zA^{\prime}(z)A(z)} \end{align*}

showing (5) and so the validity of (1). Here we use in (*) the relationship (6).