Take the 2-minute tour ×
Mathematics Stack Exchange is a question and answer site for people studying math at any level and professionals in related fields. It's 100% free, no registration required.

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?

share|improve this question
    
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
2  
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
show 3 more comments

2 Answers

up vote 4 down vote accepted

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.

share|improve this answer
add comment

The equation under consideration can be proved using the species of labelled rooted trees and its functional equation. (Note: we will use the letter $T$ to refer to rooted labelled trees and their generating function and $Q$ to unrooted ones in order to adhere to established convention.)

Now the species $\mathcal{T}$ of rooted labelled trees is given by $$\mathcal{T} = \mathcal{Z} \times \mathfrak{P}(\mathcal{T}).$$ This immediately gives the classic functional equation $$T(z) = z e^{T(z)}$$ where $$T(z) = \sum_{n\ge 1} T_n \frac{z^n}{n!}.$$

Differentiate to obtain a recurrence, getting $$T'(z) = e^{T(z)} + z e^{T(z)} T'(z) = \frac{T(z)}{z} + T(z) T'(z).$$ Now observe that $$T'(z) = \sum_{n\ge 0} T_{n+1} \frac{z^n}{n!} \quad\text{and}\quad \frac{T(z)}{z} = \sum_{n\ge 0} \frac{T_{n+1}}{n+1} \frac{z^n}{n!}.$$

Comparing coefficients in the differentiated functional equation and using the convolution of exponential generating functions we find that $$T_{n+1} = \frac{T_{n+1}}{n+1} + \sum_{k=0}^{n-1} {n\choose k} T_{k+1} T_{n-k}.$$

Now switch to unrooted trees noting that for the count $Q_n$ of unrooted labelled trees we have $$n \times Q_n = T_n$$ to obtain that

$$(n+1) Q_{n+1} = Q_{n+1} + \sum_{k=0}^{n-1} {n\choose k}\times (k+1) Q_{k+1}\times (n-k) Q_{n-k}.$$ This yields $$Q_{n+1} = \frac{1}{n} \sum_{k=1}^n {n\choose k-1} \times k Q_k \times (n+1-k) Q_{n+1-k} \\= \sum_{k=1}^n \frac{(n-1)!}{(k-1)!(n-k)!} \times k Q_k \times Q_{n+1-k} \\ = \sum_{k=1}^n {n-1\choose k-1} \times k Q_k \times Q_{n+1-k}.$$ This is what we were trying to prove (replacing $n+1$ by $n$), QED.

share|improve this answer
add comment

Your Answer

 
discard

By posting your answer, you agree to the privacy policy and terms of service.

Not the answer you're looking for? Browse other questions tagged or ask your own question.