
# 3.6: Catalan Numbers


A rooted binary tree is a type of graph that is particularly of interest in some areas of computer science. A typical rooted binary tree is shown in Figure $$\PageIndex{1}$$. The root is the topmost vertex. The vertices below a vertex and connected to it by an edge are the children of the vertex. It is a binary tree because all vertices have 0, 1, or 2 children. How many different rooted binary trees are there with $$n$$ vertices?

Let us denote this number by $$C_n$$; these are the Catalan numbers. For convenience, we allow a rooted binary tree to be empty, and let $$C_0=1$$. Then it is easy to see that $$C_1=1$$ and $$C_2=2$$, and not hard to see that $$C_3=5$$. Notice that any rooted binary tree on at least one vertex can be viewed as two (possibly empty) binary trees joined into a new tree by introducing a new root vertex and making the children of this root the two roots of the original trees; see Figure $$\PageIndex{2}$$. (To make the empty tree a child of the new vertex, simply do nothing, that is, omit the corresponding child.)

Thus, to make all possible binary trees with $$n$$ vertices, we start with a root vertex, and then for its two children insert rooted binary trees on $$k$$ and $$l$$ vertices, with $$k+l=n-1$$, for all possible choices of the smaller trees. Now we can write

3.6: Catalan Numbers is shared under a CC BY-NC-SA 3.0 license and was authored, remixed, and/or curated by David Guichard.