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}$ How to prove the combinatoric identity
$$\sum _{k=1}^{n-1} \binom{n-1}{k} k^{k-1} (n-k)^{n-k-1}=n^{n-1}-n^{n-2}$$
My bet is on binomial theorem but I don't know how. I've also considered to transform it into an integral but the $k^k$ term is annoying. Any help will be appreciated.
 A: 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. 
A: 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!}$$
A: 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).

