# An identity on the number of trees

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?

-
Clarification: $T_n$ is the number of labelled trees on $n$ vertices, right? Can you specify that in the question as well? – Srivatsan Sep 19 '11 at 2:37
yes, you're right. I will specify – Alex M Sep 19 '11 at 3:06
On a lark, would you happen to have seen this? – J. M. Sep 19 '11 at 3:18
Hint: Take a tree with vertices $\{ 1,2,\ldots, n \}$. There is a unique edge $e$ incident to vertex $1$ such that $n$ is on the other side of $e$ from $1$. Delete $e$, leaving two trees behind. Now, someone else finish the argument from here... – David Speyer Sep 19 '11 at 18:25
Continuing Davidâ€™s hint: Let $k$ be the number of vertices in the tree containing vertex $n$. How many possible sets of vertices are there for the subtree with $k$ vertices? – Brian M. Scott Sep 19 '11 at 19:54
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.