Catalan Numbers: Counting Balanced Structures

What Are Catalan Numbers?

Catalan numbers are a sequence of natural numbers that appear in various counting problems, often involving recursively defined objects. The nth Catalan number is given by the formula C(n) = (1/(n+1)) * (2n choose n).

These numbers first appeared in the work of Eugène Charles Catalan in 1838 but have since been found to count a variety of combinatorial structures.

Balanced Structures

Catalan numbers can be used to count the number of ways to correctly match n pairs of parentheses. For example, for n=2, there are two valid sequences: (()) and ()().

Another interpretation involves counting the number of full binary trees with n+1 leaves. A full binary tree is a tree in which every node has either 0 or 2 children.

Lattice Paths

Catalan numbers also count the number of lattice paths from (0,0) to (n,n) that do not cross above the diagonal y=x. These paths are made up of steps right and up.

For instance, for n=2, there are 2 such paths: one going directly east twice and then north, and another going northeast once and then northwest.

Real-World Applications

Catalan numbers have applications in computer science, particularly in parsing expressions with nested parentheses and in the analysis of algorithms.

In biology, they can be used to model RNA secondary structures, where each base pair is a balanced parenthesis.

Frequently asked questions

Try it live

Everything above runs in your browser — open Catalan Numbers — Structures, One by One (2D) and change the parameters while it is running. Nothing is installed, nothing is uploaded, the whole model lives in one tab.