Prove recursive formula for number of spanning trees in complete graph. When $t(n)$ is number of spanning trees in complete graph $K_n$ prove recursive formula for $t(n)$:  $$t(n) = {1\over (n-1)}\sum_{k=1}^{n-1} k(n-k){n-1 \choose k-1}t(k)t(n-k)$$
Could someone prove it or at least help somehow? I can use any method and Cayley's formula( $t(n)=n^{(n-2)}$) which I have already proven. 
 A: I see it now.
Let the vertices be $1,2,\dots,n$.  Partition the vertices into nonempty sets $V_1,V_2$ where $1\in V_1$.  There are ${n-1\choose k-1}$ ways to do this so that $|V_1|=k$.  Let $G_i$ be the subgraph induced by $V_i,\ i=1,2.$  There are $t(k)$ spanning trees of $G_1$ and $t(n-k)$ spanning trees of $G_2$.  To get a spanning tree of $K_n$ we need an edge joining the two spanning trees.  There are $k$ choices from $V_1$ and $n-k$ choices from $V_2.$
This accounts for everything except the factor of ${1\over n-1}.$  I claim that every spanning tree $T$ is counted exactly $n-1$ times in the above construction.  Let $uv$ be an edge of $T$.  Deleting $uv$ from $T$ separates T into two trees $T_1$ and $T_2$ where we may assume that $1$ is one of the vertices in $T_1$.  Let $V_1$ be the vertex set of $T_1$ and $V_2$ be the vertex set of $T_2$.  Then $T$ is produced by the above construction, where we join $u$ and $v$ at the last step.  Thus, $T$ is produced once for each edge, or $n-1$ times.
Substituting $n^{n-2}$ for $t(n)$ everywhere gives an amazing looking formula doesn't it?    
A: (migrated answer from duplicate).
With the number of spanning trees in a complete graph
being $n^{n-2}$ we seek to show that
$$n^{n-2} (n-1) =
\sum_{q=1}^{n-1} q(n-q) {n-1\choose q-1}
q^{q-2} (n-q)^{n-q-2}
\\ =\sum_{q=1}^{n-1} q(n-q) \frac{q}{n} {n\choose q}
q^{q-2} (n-q)^{n-q-2}
= \frac{1}{n} \sum_{q=1}^{n-1} {n\choose q}
q^{q} (n-q)^{n-q-1}.$$
This means we need
$$n^{n-1} (n-1) =
\sum_{q=1}^{n-1} {n\choose q}
q^{q} (n-q)^{n-q-1}.$$
This  sum  has  EGF given  by  the  product  of  two EGFs  $A(z)$  and
$B(z)$, which are as follows:
$$A(z) = \sum_{q\ge 1} q^q \frac{z^q}{q!}
\quad\text{and}\quad
B(z) = \sum_{q\ge 1} q^{q-1} \frac{z^q}{q!}.$$
We recognize $B(z)$ as the labeled tree function $T(z)$
with functional equation
$$T(z) = z \exp T(z).$$
Furthermore we have by inspection that
$$A(z) = z T'(z).$$
Our claim thus reduces to
$$n^{n-1} (n-1) =
n! [z^n] A(z) B(z) = n! [z^n] z T(z) T'(z).$$
Note that the sum in the  convolution ranges from $q=1$ to $q=n-1$ but
we may include $q=0$ and $q=n$ because  $[z^0] A(z) = [z^0] B(z) = 0,$
yielding a proper convolution of two EGFs. 
We have from the Cauchy Coefficient Formula that
$$n! [z^n] z T(z) T'(z) =
\frac{n!}{2\pi i}
\int_{|z|=\epsilon} \frac{1}{z^{n+1}}
z T(z) T'(z) \; dz.$$
Now put $T(z) = w$ so that $T'(z) \; dz = dw$ and $z = w \exp(-w)$
to obtain
$$\frac{n!}{2\pi i}
\int_{|w|=\gamma} \frac{\exp(nw)}{w^{n}}
w \; dw
= \frac{n!}{2\pi i}
\int_{|w|=\gamma} \frac{\exp(nw)}{w^{n-1}}\; dw.$$
This is
$$n! [w^{n-2}] \exp(nw) = n! \frac{n^{n-2}}{(n-2)!}
= n (n-1) n^{n-2} = n^{n-1} (n-1)$$
and we have the claim.
 Remark.  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_{q=0}^n \frac{1}{q!}\frac{1}{(n-q)!} a_q b_{n-q} z^n\\
= \sum_{n\ge 0}
\sum_{q=0}^n \frac{n!}{q!(n-q)!} a_q b_{n-q} \frac{z^n}{n!}
= \sum_{n\ge 0}
\left(\sum_{q=0}^n {n\choose q} a_q b_{n-q}\right)\frac{z^n}{n!}$$
i.e. the  product of the  two generating functions is  the exponential
generating function of $$\sum_{q=0}^n {n\choose q} a_q b_{n-q}.$$
