How to prove the number of ordered tree with $n+1$ vertices satisfies the Catalan recurrence

Question

Let $a_{n}$ be the number of ordered tree with $n+1$ vertices. How to prove $a_{n}$ satisfies the Catalan recurrence i.e. trying to prove it satisfies $a_{n} =\sum_{k=1}^{n}a_{k-1}a_{n-k}$ for $n\geq 1$ with $a_{0} = 1$.

I'm stuck at figuring out what should I partition on, i.e. what does $k$ represent in the proof combinatorially?

Answer 1

Every ordered tree $T$ with $n+1$ vertices can be uniquely be built from two ordered trees $T_1$ and $T_2$ such that $T_1$ has $k$ vertices and $T_2$ has $n-k+1$ vertices.

To build $T$ from $T_1$ and $T_2$, have the root of $T_2$ "adopt" $T_1$ as its left-most child.

   T1           T2                           T
 
   A             B                           B
 / | \          / \       ==>              / | \
A  A  A        B   B                      A  B  B
                   |                    / | \   |
                   B                   A  A  A  B

This is a bijection, since you can uniquely decompose $T$ into the $T_1$ and $T_2$ that built it by "disowning" the leftmost child of the root of $T$.

Since the number of ways to choose $T_1$ and $T_2$ for a given $k$ is $a_{k-1}a_{n-k}$, the recurrence follows.