Prove this binomial sum Following problem is interesting
Show that:
$$\sum_{i=1}^{n-1}\binom{n-1}{i} i^{i-1}(n-i)^{n-i-1}=n^{n-1}-n^{n-2}$$
 A: This  computation   is  very   similar  to  the   one  at   this  MSE
link.

We  can  prove this  using  the labelled  tree
function that is known from combinatorics.

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

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

The species of labelled trees has the specification
$$\mathcal{T} = 
\mathcal{Z} \times \mathfrak{P}(\mathcal{T})$$
which gives the functional equation
$$T(z) = z \exp T(z).$$

We have $n!  [z^n] T(z) = n^{n-1}$, for a proof  consult the link from
the introduction. This implies that
$$T'(z) = \sum_{n\ge 1} n^{n-1} \frac{z^{n-1}}{(n-1)!}
= \sum_{n\ge 0} (n+1)^{n} \frac{z^{n}}{n!}.$$

Simplify using
$$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
$$T'(z) = \frac{1}{z} \frac{T(z)}{1-T(z)}.$$
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) = T(z) \quad\text{and}\quad B(z) = T'(z) =
\frac{1}{z} \frac{T(z)}{1-T(z)}.$$
The  equality  that  we seek  to  prove  is  the convolution of the  two
exponential generating functions $A(z)$ and $B(z)$ and to verify it we
must show that
$$n! [z^n] A(z) B(z) = n \times (n+1)^{n-1}$$
But we have 
$$A(z) B(z) = \frac{1}{z} \frac{T(z)^2}{1- T(z)}.$$
It follows that
$$n! [z^n] A(z) B(z)
= n! \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} 
\frac{1}{z} \frac{T(z)^2}{1- T(z)}  dz.$$
Using the same substitution as before (consult link) this becomes
$$n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(n+2))}{w^{n+2}} 
\times \frac{w^2}{1-w} \times (\exp(-w) - w\exp(-w)) dw
\\ = n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(n+1))}{w^{n}} dw
\\ = n!
\frac{(n+1)^{n-1}}{(n-1)!}
= n \times (n+1)^{n-1}.$$

The labelled tree function recently appeared at this 
MSE link.
