$$\newcommand{\id}{\mathrm{id}}$$ $$\newcommand{\Span}{\mathrm{span}}$$ $$\newcommand{\kernel}{\mathrm{null}\,}$$ $$\newcommand{\range}{\mathrm{range}\,}$$ $$\newcommand{\RealPart}{\mathrm{Re}}$$ $$\newcommand{\ImaginaryPart}{\mathrm{Im}}$$ $$\newcommand{\Argument}{\mathrm{Arg}}$$ $$\newcommand{\norm}[1]{\| #1 \|}$$ $$\newcommand{\inner}[2]{\langle #1, #2 \rangle}$$ $$\newcommand{\Span}{\mathrm{span}}$$
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?
Figure $$\PageIndex{1}$$: A rooted binary tree.
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{1}$$. (To make the empty tree a child of the new vertex, simply do nothing, that is, omit the corresponding child.)