How to answer the following question related to counting the number of trees of a graph? I am asked to prove the equality $$ 2(n-1)n^{n-2} = \sum_{k=1}^{n-1} \binom{n}{k} k(n-k)T(k)T(n-k) ,  $$
where $T(k)$ is the number of different trees with $k$ numbered vertices. 
I think the following theorem (in my textbook) could help proving this fact: 
Theorem: Let $T(n,p)$ be the number of graphs with numbered vertices $v_{1} , \dots , v_{n}$ consisting of $p$ disjunct trees such that $v_{i}$ belongs to the $i$'th tree, where $1 \leq i \leq p $. Then it is true that: $T(n,p) = p n^{n-p-1}$. 
This theorem is proved by first showing that the following recursive formula holds: 
$$ T(n,p) = \sum_{j=0}^{n-p} \binom{n-p}{j} T(n-1,p+j-1) .$$
Questions: Could this theorem and the recursive formula I mentioned help prove the equality? If so, how? If not, what would be a better way to prove the equality? 
 A: We  can  prove this  using  the labelled  tree
function that is known from combinatorics.

Suppose we seek to verify that
$$2(n-1) n^{n-2} =
\sum_{k=1}^{n-1} {n\choose k} k(n-k) Q_k Q_{n-k}$$
where $Q_k$ is the number of unrooted labeled trees on $k$ nodes.
This is the same as evaluating
$$\sum_{k=1}^{n-1} {n\choose k} T_k T_{n-k}$$
where $T_k$ is the number of rooted labeled trees on $k$ nodes.
We have multiplied $Q_k$ by $k$, reflecting the $k$ choices for 
the root.

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

The combinatorial class of rooted 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).$$

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}.$$

Now  since $[z^0]  T(z)  = 0$  we  may write  for  the convolution  in
question that it is
$$\sum_{k=0}^{n} {n\choose k} T_k T_{n-k}.$$
Therefore we are dealing with the scenario
$$A(z) = B(z) = 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) = 2 (n-1) n^{n-2}$$
We thus compute
$$n! [z^n] A(z) B(z)
= n! \frac{1}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}} T(z)^2 dz.$$
Put $T(z) = w$ to get $z=w\exp(-w)$ and $dz = (\exp(-w)-w\exp(-w)) \; dw$
to obtain
$$n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(w(n+1))}{w^{n+1}} 
\times w^2\times (\exp(-w) - w\exp(-w)) \; dw
\\ = n! \frac{1}{2\pi i}
\int_{|w|=\epsilon} 
\frac{\exp(wn)}{w^{n-1}} (1-w) \; dw
\\ = n!
\left(\frac{n^{n-2}}{(n-2)!} - \frac{n^{n-3}}{(n-3)!}\right).$$
This is
$$n^{n-2} (n(n-1)-(n-1)(n-2))
= n^{n-2} (n^2-n-n^2+3n-2) 
\\ = n^{n-2} \times (2n-2)$$
as claimed.

The labelled tree function recently appeared at this 
MSE link.
