Prove recursive formula for number of spanning trees in complete graph.

Question

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.

Answer 1

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?

Answer 2

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