Loading [MathJax]/jax/output/HTML-CSS/jax.js
Skip to main content
Library homepage
 

Text Color

Text Size

 

Margin Size

 

Font Type

Enable Dyslexic Font
Mathematics LibreTexts

3.6: Catalan Numbers

( \newcommand{\kernel}{\mathrm{null}\,}\)

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 3.6.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?

3.5.1.png
Figure 3.6.1: A rooted binary tree.

Let us denote this number by Cn; these are the Catalan numbers. For convenience, we allow a rooted binary tree to be empty, and let C0=1. Then it is easy to see that C1=1 and C2=2, and not hard to see that C3=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 3.6.2. (To make the empty tree a child of the new vertex, simply do nothing, that is, omit the corresponding child.)

3.5.2.png
Figure 3.6.2: Producing a new tree from smaller trees.

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=n1, for all possible choices of the smaller trees. Now we can write

Cn=n1i=0CiCni1.

For example, since we know that C0=C1=1 and C2=2,

C3=C0C2+C1C1+C2C0=12+11+21=5,

as mentioned above. Once we know the trees on 0, 1, and 2 vertices, we can combine them in all possible ways to list the trees on 3 vertices, as shown in Figure 3.6.3. Note that the first two trees have no left child, since the only tree on 0 vertices is empty, and likewise the last two have no right child.

3.5.3.png
Figure 3.6.3: The 3-vertex binary rooted trees.

Now we use a generating function to find a formula for Cn. Let f=i=0Cixi. Now consider f2: the coefficient of the term xn in the expansion of f2 is ni=0CiCni, corresponding to all possible ways to multiply terms of f to get an xn term: C0Cnxn+C1xCn1xn1+C2x2Cn2xn2++CnxnC0. Now we recognize this as precisely the sum that gives Cn+1, so f2=n=0Cn+1xn. If we multiply this by x and add 1 (which is C0) we get exactly f again, that is, xf2+1=f or xf2f+1=0; here 0 is the zero function, that is, xf2f+1 is 0 for all x. Using the quadratic formula,

f=1±14x2x,

as long as x0. It is not hard to see that as x approaches 0,

1+14x2x

goes to infinity while

114x2x

goes to 1. Since we know f(0)=C0=1, this is the f we want.

Now by Newton's Binomial Theorem, we can expand

14x=(1+(4x))1/2=n=0(1/2n)(4x)n.

Then

114x2x=n=112(1/2n)(4)nxn1=n=012(1/2n+1)(4)n+1xn.

Expanding the binomial coefficient (1/2n+1) and reorganizing the expression, we discover that

Cn=12(1/2n+1)(4)n+1=1n+1(2nn).

In Exercise 1.E.3.7 in Section 1.E, we saw that the number of properly matched sequences of parentheses of length 2n is (2nn)(2nn+1), and called this Cn. It is not difficult to see that

(2nn)(2nn+1)=1n+1(2nn),

so the formulas are in agreement.

Temporarily let An be the number of properly matched sequences of parentheses of length 2n, so from the exercise we know An=(2nn)(2nn+1). It is possible to see directly that A0=A1=1 and that the numbers An satisfy the same recurrence relation as do the Cn, which implies that An=Cn, without manipulating the generating function.

There are many counting problems whose answers turns out to be the Catalan numbers. Enumerative Combinatorics: Volume 2, by Richard Stanley, contains a large number of examples.


This page titled 3.6: Catalan Numbers is shared under a CC BY-NC-SA 4.0 license and was authored, remixed, and/or curated by David Guichard via source content that was edited to the style and standards of the LibreTexts platform.

Support Center

How can we help?