An identity on the number of trees

227 Views Asked by At

Let $T_n$ be the number of labelled trees on $n$ vertices, then

$$ T_n=\sum_kk\binom{n-2}{k-1}T_kT_{n-k} \tag{1}$$

Using this question, I was able to prove that

$$ T_n= \frac{n}{2} \ \sum\binom{n-2}{k-1}T_kT_{n-k} .$$

But I don't know how to prove $(1)$. Can anyone help me please?

1

There are 1 best solutions below

0
On BEST ANSWER

I incidentally came on this post. The OP was on the right path. He proved that $$T_n=\frac{n}{2}\sum_k\binom{n-2}{k-1}T_kT_{n-k}.$$ This is euqivalent to say $$\begin{eqnarray}2T_n&=&\sum_k(k+(n-k))\binom{n-2}{k-1}T_kT_{n-k}\\ &=&\sum_k\left(k\binom{n-2}{k-1}T_kT_{n-k}+(n-k)\binom{n-2}{n-k-1}T_{n-k}{T_k}\right)\\&=&\sum_kk\binom{n-2}{k-1}T_kT_{n-k}+\sum_jk\binom{n-2}{j-1}T_jT_{n-j}\\ &=&2\sum_kk\binom{n-2}{k-1}T_nT_{n-k}.\end{eqnarray}$$ From which the result follows.