Rooted Binary Trees and Catalan Numbers

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:

(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!

• There is a very useful recursive characterisation of $C_n$. Wikipedia has it. Sep 27, 2016 at 23:40
• 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. Sep 27, 2016 at 23:44

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}$.

• Could you explain why the recurrence works for the Catalan numbers? Thanks! Sep 28, 2016 at 1:15
• You can find it here: math.stackexchange.com/questions/1192408/… Sep 28, 2016 at 17:01