Proving $ 2n^{n-3} = \sum\limits_{i=1}^{n-1}\binom{n-2}{i-1}i^{\ i-2}(n-i)^{\ n-i-2} $ My question is how to show$$ 2n^{n-3} = \sum_{i=1}^{n-1}\binom{n-2}{i-1}i^{\ i-2}(n-i)^{\ n-i-2} $$
I got to this result through a problem of counting labeled trees, but when I try to approach actually computing the sum, I've had no breakthroughs. 
 A: Your result is a special case (setting $x=y=1$, $m=n-2$ and changing to summation index $i=k+1$) of the identity
$$
\sum_{k=0}^m{m\choose k}(x+k)^{k-1}(y+m-k)^{m-k-1}=
\left(\frac1x+\frac1y\right)(x+y+m)^{m-1}\tag2
$$
which in turn follows from a version of Abel's Binomial Theorem:
$$
\sum_{k=0}^n{n\choose k}x(x+kz)^{k-1}(y+(n-k)z)^{n-k}=(x+y+nz)^n\tag1
$$
The proof of (1) (and the equation numbering I've used) can be found here, which also explains how to get (2) from (1). The proof, which is rather involved, proceeds by differentiating both sides of (1) with respect to $y$ and then applying induction on $n$. (Maybe you can assume identity (1) is "well known".)
The cited paper mentions in passing a generalization of Abel's Binomial Theorem, known as Hurwitz' Binomial Theorem, and remarks that the simplest proof of the Hurwitz theorem involves ... counting trees. For another angle, see this.
A: Start by re-writing as follows:
$$2n^{n-3} = \sum_{k=0}^{n-2} 
{n-2\choose k} (k+1)^{k-1} (n-1-k)^{n-3-k}$$
so that we seek to verify that
$$\bbox[5px,border:2px solid #00A000]{
Q_n = \sum_{k=0}^n {n\choose k}
(k+1)^{k-1} (n+1-k)^{n-1-k} = 2(n+2)^{n-1}.}$$
Concerning the exponential generating function for this quantity
$$Q(z) = \sum_{n\ge 0} Q_n \frac{z^n}{n!}$$
we 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}.$$

Therefore  what  we have  here  is  a  convolution of  the  generating
function
$$A(z) = B(z) = \sum_{n\ge 0} (n+1)^{n-1} \frac{z^n}{n!}$$
with itself.
The combinatorial class 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 find
$$n! [z^n] T(z) = \frac{n!}{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)$ 
to get
$$\frac{n!}{2\pi i}
\int_{|w|=\gamma} 
\frac{\exp(w(n+1))}{w^{n+1}} 
\times w\times (\exp(-w) - w\exp(-w)) \; dw
\\ = \frac{n!}{2\pi i}
\int_{|w|=\gamma} 
\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_{n\ge 1} n^{n-1} \frac{z^n}{n!}.$$
Obviously this follows by inspection from Cayley's theorem.
Repeating the  same calculation to  extract coefficients on  $T(z)^2$ we
obtain
$$n! [z^n] T(z)^2 = 
n! \times \left(\frac{n^{n-2}}{(n-2)!} - \frac{n^{n-3}}{(n-3)!}\right)
\\= n(n-1) n^{n-2} - (n-1)(n-2) n^{n-2}
= (2n - 2) n^{n-2}$$
so that
$$\sum_{n\ge 1} n^{n-2} \frac{z^n}{n!}
= T(z) - \frac{1}{2} T(z)^2.$$
Hence
$$A(z) = T'(z) - T(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
$$T'(z) = \frac{1}{z} \frac{T(z)}{1-T(z)}.$$
This yields for $A(z)$ that
$$A(z) = \frac{1}{z} \frac{T(z)}{1-T(z)} (1-T(z))
= \frac{1}{z} T(z).$$
On seeing this we realize in retrospect that we could have obtained it
by inspection.  Continuing we obtain the coefficient extractor
$$n! [z^n] A(z)^2 =
\frac{n!}{2\pi i}
\int_{|w|=\gamma} 
\frac{\exp(w(n+3))}{w^{n+3}} 
\times w^2\times (\exp(-w) - w\exp(-w)) \; dw
\\ = \frac{n!}{2\pi i}
\int_{|w|=\gamma} 
\frac{\exp(w(n+2))}{w^{n+1}} (1 - w) \; dw.$$
We find
$$n! \times
 \left(\frac{(n+2)^n}{n!} - \frac{(n+2)^{n-1}}{(n-1)!}\right)
= (n+2) (n+2)^{n-1} - n (n+2)^{n-1}$$
which is
$$\bbox[5px,border:2px solid #00A000]{Q_n = 2 (n+2)^{n-1}}$$
and we have the claim.

The labelled tree function recently appeared at this 
MSE link.
