6
$\begingroup$

To form a rooted binary tree, we start with a root node. We can then stop, or draw exactly $2$ branches from the root to new nodes. From each of these new nodes, we can then stop or draw exactly $2$ branches to new nodes, and so on. We refer to a node as a parent node if we have drawn branches from it.

This diagram shows all distinct rooted binary trees with at most $0,$ $1,$ $2,$ or $3$ parent nodes: Diagram

(Note that, in the diagram, the roots are at the top and the branches extend downward -- somewhat contrary to what you'd expect for something called a "tree"!)

Prove that the number of distinct rooted binary trees with exactly $n$ parent nodes is the $n^{\text{th}}$ Catalan number.


To count the number of rooted binary trees, I think you do something with a power of 2, because there's two choices at each point. But that's all I have. And for the Catalan numbers, which is $C_n = \frac 1{n+1}\binom{2n}n,$ and I don't understand the other recurrence, if you could explain that, it would be great. Can someone walk me through this problem? Thanks in advance!

$\endgroup$
  • 2
    $\begingroup$ There is a very useful recursive characterisation of $C_n$. Wikipedia has it. $\endgroup$ – Stanley Sep 27 '16 at 23:40
  • $\begingroup$ I will note that in some schools (I can't remember which) trees are drawn with the root at the bottom. In phylogenetics, trees are often drawn with the root on the left and the tree drawn to right or even the root in the center and the branches drawn out in a circle. $\endgroup$ – Mosquite Sep 27 '16 at 23:44
5
$\begingroup$

Catalan numbers satisfy the recurrence:

$C_0 = 1, C_{n+1} = \sum_{i=0}^nC_iC_{n-i}, n \geq 0$

So it suffices that show that binary trees satisfy the same recurrence.

Let $T_n$ be the number of binary trees with $n$ parent nodes.

There is 1 tree with zero parent nodes. So $T_0=1$.

For $n \geq 0$: A tree $t$ with $n+1$ parent nodes has a root with two subtrees as children $t_1$ and $t_2$. Since the root of $t$ is a parent node, $t_1$ and $t_2$ must have $n$ parent nodes together (i.e. if $t_1$ has $i$ parent nodes then $t_2$ has $n-i$ parent nodes). Then the number of ways to make children $t_1$ and $t_2$ is $\sum_{i=0}^nT_iT_{n-i}$.

| cite | improve this answer | |
$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

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