Catalan Number — Definition, Formula & Examples

A Catalan number is a member of the sequence 1, 1, 2, 5, 14, 42, 132, ... that counts the number of ways to perform various combinatorial tasks, such as correctly matching parentheses or triangulating a polygon.

The $n$ -th Catalan number $C_n$ is defined as $\frac{1}{n+1}\binom{2n}{n}$ for $n \geq 0$ . Equivalently, $C_n$ satisfies the recurrence $C_0 = 1$ and $C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i}$ for $n \geq 0$ .

Key Formula

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

Where:

$C_n$ = The $n$-th Catalan number ($n \geq 0$)
$n$ = A non-negative integer index
$\binom{2n}{n}$ = The central binomial coefficient, equal to $\frac{(2n)!}{n!\, n!}$

How It Works

You can compute Catalan numbers directly from the closed-form formula or build them up iteratively using the recurrence. The closed-form involves a single binomial coefficient divided by

n+1

, which always yields an integer. Many counting problems reduce to Catalan numbers: the number of valid arrangements of

n

pairs of parentheses, the number of distinct binary trees with

n

internal nodes, the number of paths on an

n \times n

grid that stay below the diagonal, and the number of ways to triangulate a convex polygon with

n+2

sides.

Worked Example

Problem: How many distinct ways can you arrange 4 pairs of parentheses so that every opening parenthesis is properly closed?

Identify n: With 4 pairs of parentheses, we need

C_4

n = 4

Apply the formula: Substitute

n = 4

into the closed-form expression.

C_4 = \frac{1}{5}\binom{8}{4} = \frac{1}{5} \cdot \frac{8!}{4!\,4!}

Compute: Evaluate the binomial coefficient and divide.

\binom{8}{4} = 70, \quad C_4 = \frac{70}{5} = 14

Answer: There are 14 valid arrangements of 4 pairs of parentheses.

Visualization

Why It Matters

Catalan numbers appear across discrete mathematics, computer science, and algorithm design. They count binary search tree structures (relevant to data structure analysis), parse trees in compiler theory, and lattice path configurations in probability. Any course in combinatorics or algorithms will encounter them repeatedly.

Common Mistakes

Mistake: Forgetting the

\frac{1}{n+1}

factor and reporting the central binomial coefficient

\binom{2n}{n}

as the Catalan number.

Correction: The Catalan number is always

\binom{2n}{n}

divided by

n+1

. Without this factor you get a much larger number that overcounts by including invalid configurations.