Cayley's formula summation form

169 Views Asked by At

I need to see how

$T_n=\sum_{i=1}^{n-1}\frac{1}{n-1}i(n-i){n-1\choose i-1}T_iT_{n-i}$

where $T_n$ denotes number of trees in a complete graph on $n$ vertices.

I have found out that # trees with one fixed edge is equal to

$E_n =\sum_{i=1}^{n-1}{n-2 \choose i-1}T_iT_{n-i}$

however I am not sure how to continue.

1

There are 1 best solutions below

1
On

More straightforward way:

Let's rewrite $S_1 = \sum\limits_{i=1}^{n-1}\frac{1}{n-1}i(n-i){n-1\choose i-1}T_iT_{n-i}$ by performing a change $i \mapsto n - i$, giving $S_2 = \sum\limits_{i=1}^{n-1}\frac{1}{n-1}i(n-i){n-1\choose n -i-1}T_iT_{n-i} = \sum\limits_{i=1}^{n-1}\frac{1}{n-1}i(n-i){n-1\choose i}T_iT_{n-i}$.

Now $\frac{1}{2}(S_1 + S_2)$ is just $\sum\limits_{i=1}^{n-1}\frac{1}{2\cdot(n-1)}i(n-i){n\choose i}T_iT_{n-i}$, and we want to prove:

$$T_n \cdot 2\cdot(n - 1) = \sum\limits_{i=1}^{n-1}i(n-i){n\choose i}T_iT_{n-i} $$ The LHS is the number of spanning trees with chosen oriented edge. So is the RHS, because it is the number of ways to choose $i$ vertices, draw trees of size $i$ and $n - i$ and connect by an edge coming from tree of size $i$ to tree of size $n - i$.