Rooted Binary Trees and Catalan Numbers

Question

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!

Answer 1

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