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. 

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.
