5
$\begingroup$

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?

  • 0
    Clarification: $T_n$ is the number of *labelled* trees on $n$ vertices, right? Can you specify that in the question as well?2011-09-19
  • 0
    yes, you're right. I will specify2011-09-19
  • 2
    On a lark, would you happen to have seen [this](http://people.brandeis.edu/~gessel/homepage/students/drakethesis.pdf)?2011-09-19
  • 0
    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...2011-09-19
  • 0
    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?2011-09-19
  • 0
    @David: why is there an edge connecting 1 and $n$?2011-09-19
  • 0
    There isn't necessarily an edge which immediately connects $1$ and $n$. There is an edge $e$ such that $1$ is incident to $e$ and removing $e$ separates $1$ from $n$. (Why?)2011-09-19
  • 0
    ah ok ok, now it's clear. Thank you2011-09-19

2 Answers 2

4

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.

1

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.