Catalan Number Generator

What is a Catalan Number?

The Catalan numbers form one of the most important sequences in combinatorics. Named after the Belgian mathematician Eugene Charles Catalan (1814-1894), these numbers appear in over 200 distinct counting problems across mathematics, computer science, and physics. The sequence begins: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, ...

Surprisingly, Catalan numbers were first discovered by Leonhard Euler in the 1750s when he counted the number of ways to triangulate a convex polygon. Today, they are catalogued as sequence A000108 in the OEIS (Online Encyclopedia of Integer Sequences) and are essential in fields ranging from algebraic geometry to theoretical computer science.

Catalan Number Formula

The n-th Catalan number $C_n$ can be expressed using a closed-form formula involving binomial coefficients:

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!}$$

For example, $C_3 = \frac{1}{4}\binom{6}{3} = \frac{20}{4} = 5$, confirming that there are exactly 5 ways to correctly match 3 pairs of parentheses: ((())), (()()), (())(), ()(()), and ()()().

Recurrence Relation

Catalan numbers also satisfy a simple recurrence relation, which makes them easy to compute even for large values of n:

$$C_0 = 1, \quad C_{n+1} = \sum_{i=0}^{n} C_i\,C_{n-i} = \frac{2(2n+1)}{n+2}\,C_n$$

Using the recurrence form $C_n = \frac{2(2n-1)}{n+1} \cdot C_{n-1}$, our tool efficiently computes Catalan numbers up to $C_{500}$ using JavaScript BigInt arithmetic, ensuring exact integer results without floating-point errors.

Combinatorial Interpretations

Catalan numbers answer an extraordinary range of counting questions. Here are the most important interpretations:

Balanced Parentheses

$C_n$ counts the number of ways to correctly match n pairs of parentheses. For n = 3, there are exactly 5 valid arrangements: ((())), (()()), (())(), ()(()), and ()()(). This is the most intuitive interpretation and our tool automatically displays all valid parenthesizations for n up to 6.

Dyck Paths

$C_n$ is the number of Dyck paths monotonic lattice paths from (0,0) to (2n,0) using steps U = (1,1) and D = (1,-1) that never go below the x-axis. Our tool visualizes these paths for small n, showing the characteristic mountain range shape.

Polygon Triangulations

$C_{n-2}$ counts the number of ways to triangulate a convex polygon with n sides by drawing non-crossing diagonals. This was Euler's original problem.

Full Binary Trees

$C_n$ counts the number of full binary trees (where every node has 0 or 2 children) with n+1 leaves. This is closely related to the number of distinct binary search trees with n keys, a classic problem in computer science.

Non-Crossing Partitions

$C_n$ equals the number of non-crossing partitions of the set {1, 2, ..., n} where no two blocks cross when drawn on a circle.

Applications in Computer Science

Catalan numbers appear throughout computer science:

• Binary Search Trees: $C_n$ counts distinct BSTs with n keys.
• Matrix Chain Multiplication: $C_{n-1}$ counts ways to parenthesize a product of n matrices.
• Stack-Sortable Permutations: $C_n$ counts permutations of {1,...,n} sortable by a single stack.
• Expression Parsing: $C_n$ counts distinct parse trees for expressions with n operators.
• Dynamic Programming: Catalan numbers appear as the basis for many DP problems in competitive programming.

Asymptotic Growth

Catalan numbers grow exponentially. The asymptotic formula is:

$$C_n \sim \frac{4^n}{n^{3/2}\sqrt{\pi}}$$

This means $C_n$ grows roughly as $4^n$, with a polynomial correction factor of $n^{-3/2}$. The ratio $C_n/C_{n-1}$ approaches 4 as n grows large. For perspective, $C_{10} = 16,796$, $C_{20} = 6,564,120,420$, and $C_{100}$ has 58 digits.

Our Collatz Conjecture Calculator and Fibonacci Number Generator are other popular sequence tools you might find useful.