Catalan Numbers: The Universal Counting Sequence

July 2026 · 22 min read

What Are Catalan Numbers?

The Catalan numbers form one of the most frequently occurring sequences in combinatorics. The first few values are:

C₀=1, C₁=1, C₂=2, C₃=5, C₄=14, C₅=42, C₆=132, C₇=429, …

They appear in an astonishing variety of counting problems — from the number of valid arrangements of parentheses to the number of full binary trees with n internal nodes. Eugène Charles Catalan studied them in the 1830s, but the sequence was known to Euler and even to Chinese mathematicians centuries earlier.

In competitive programming, Catalan numbers surface surprisingly often. Recognising that a problem is "secretly Catalan" can collapse a complex counting task into a single formula evaluation.

OEIS A000108. The Catalan sequence grows roughly as 4ⁿ / (n^3/2 √π), so values get large very fast. Most CP problems ask for the answer modulo a prime.

The Closed-Form Formula

The n-th Catalan number has the elegant closed form:

C_n = C(2n, n) / (n + 1)

Equivalently, using the binomial coefficient directly:

C_n = (2n)! / ((n + 1)! · n!)

Another useful form is the difference of binomial coefficients:

C_n = C(2n, n) − C(2n, n + 1)

Why this matters in CP. The difference form C(2n, n) − C(2n, n+1) avoids division entirely, which is helpful when working modulo a composite number where modular inverse may not exist.

Proof sketch (ballot problem approach): Consider paths on a grid from (0,0) to (2n,0) using steps +1 (up) and −1 (down), never going below the x-axis. The total number of unrestricted paths is C(2n, n). The number of "bad" paths (those that dip below zero) is C(2n, n+1) by the reflection principle. Subtracting gives C_n = C(2n, n) − C(2n, n+1).

Classic Interpretations

The real beauty of Catalan numbers is the sheer variety of objects they count. Here are at least five classic interpretations, each worth understanding deeply.

1. Balanced Parentheses

C_n counts the number of ways to arrange n pairs of parentheses so that they are correctly matched. For example, with n = 3:

((()))   (()())   (())()   ()(())   ()()()

That gives C₃ = 5. This is perhaps the most fundamental Catalan interpretation and maps directly to many CP problems — any time a problem reduces to "count valid sequences of two matching symbols," think Catalan.

2. Full Binary Trees

C_n is the number of distinct full binary trees (every internal node has exactly 2 children) with n internal nodes (and thus n + 1 leaves). Equivalently, it counts the number of distinct rooted binary trees with n + 1 leaves.

This interpretation is central in compiler theory (expression trees) and in problems involving recursive tree structures.

3. Triangulations of a Convex Polygon

C_n counts the number of ways to divide a convex polygon with n + 2 sides into triangles using non-crossing diagonals. For a pentagon (n = 3), there are exactly 5 triangulations.

This connects Catalan numbers to computational geometry problems. The classic "polygon triangulation" problem has a Catalan-number answer.

4. Dyck Paths

A Dyck path of length 2n is a lattice path from (0, 0) to (2n, 0) consisting of steps U = (1, 1) and D = (1, −1) that never goes below the x-axis. The number of such paths is C_n.

Dyck paths are the geometric visualization behind the ballot problem and the reflection principle proof of the Catalan formula.

5. Non-Crossing Partitions

C_n counts the number of non-crossing partitions of the set {1, 2, …, n}. A partition is non-crossing if, when we draw the elements on a circle and connect elements in the same block, no two connecting arcs cross.

For n = 4, there are C₄ = 14 non-crossing partitions.

Other Interpretations (Quick List)

Stack-sortable permutations: the number of permutations of {1, …, n} that can be sorted by a single stack.
Mountain ranges: sequences of n up-strokes and n down-strokes that never dip below the baseline.
Ballot sequences: sequences where candidate A always leads candidate B, given A and B each receive n votes.
Matrix chain multiplication: the number of ways to parenthesise a product of n + 1 matrices.

Tip: When you encounter a new counting problem in a contest, ask yourself: "Does this reduce to one of the standard Catalan interpretations?" If so, the answer is likely C_n or a product/sum involving Catalan numbers.

Recurrence Relation

Catalan numbers satisfy the recurrence:

C_n = ∑_i=0ⁿ⁻¹ C_i · C_n−1−i, with C₀ = 1

Intuition via balanced parentheses: Consider the first opening parenthesis. It must close at some position 2i + 1 (for i = 0, 1, …, n − 1). Inside it there are i pairs (counted by C_i), and after it there are n − 1 − i pairs (counted by C_n−1−i). Summing over all positions gives the recurrence.

Intuition via binary trees: Pick the structure of the left subtree (i nodes, counted by C_i) and the right subtree (n − 1 − i nodes, counted by C_n−1−i).

The recurrence runs in O(n²) time if we compute all values up to n. This is useful when the closed form is hard to evaluate (e.g., modulo a composite).

// O(n^2) DP for Catalan numbers mod p
const int MOD = 1e9 + 7;
long long catalan[5001];

void precompute(int n) {
    catalan[0] = 1;
    for (int i = 1; i <= n; i++) {
        catalan[i] = 0;
        for (int j = 0; j < i; j++) {
            catalan[i] = (catalan[i] + catalan[j] % MOD * catalan[i - 1 - j] % MOD) % MOD;
        }
    }
}

Watch out: The O(n²) DP is fine for n ≤ 5000 but too slow for large n. For n up to 10⁶ or beyond, use the closed-form formula with modular inverse.

Generating Function

The ordinary generating function (OGF) for the Catalan numbers is:

C(x) = ∑_n≥0 C_n xⁿ

From the recurrence C_n = ∑ C_i C_n−1−i, we recognise a convolution, which means:

C(x) = 1 + x · C(x)²

Solving this quadratic in C(x):

C(x) = (1 − √(1 − 4x)) / (2x)

We take the minus sign in front of the square root because we need C(0) = C₀ = 1 (the plus sign gives a series diverging at x = 0).

Deriving the closed form from the GF: Expanding √(1 − 4x) using the generalised binomial theorem gives:

√(1 − 4x) = ∑_n≥0 C(1/2, n) (−4x)ⁿ

After simplification, the coefficient of xⁿ in C(x) works out to C(2n, n) / (n + 1), confirming the closed form.

Advanced: The generating function is extremely useful for proving Catalan identities and for problems involving convolutions of Catalan sequences. In competitive programming, you rarely need the GF directly, but understanding it deepens your intuition.

Computing Catalan Numbers Efficiently

In competitive programming, we typically compute C_n modulo a large prime (usually 10⁹ + 7). The key steps are:

Precompute factorials and inverse factorials up to 2n.
Compute C(2n, n) using precomputed values.
Multiply by the modular inverse of (n + 1).

#include <bits/stdc++.h>
using namespace std;

const int MOD = 1e9 + 7;
const int MAXN = 2e6 + 5;
long long fac[MAXN], inv_fac[MAXN];

long long power(long long base, long long exp, long long mod) {
    long long result = 1;
    base %= mod;
    while (exp > 0) {
        if (exp & 1) result = result * base % mod;
        base = base * base % mod;
        exp >>= 1;
    }
    return result;
}

void precompute_factorials() {
    fac[0] = 1;
    for (int i = 1; i < MAXN; i++)
        fac[i] = fac[i - 1] * i % MOD;
    inv_fac[MAXN - 1] = power(fac[MAXN - 1], MOD - 2, MOD);
    for (int i = MAXN - 2; i >= 0; i--)
        inv_fac[i] = inv_fac[i + 1] * (i + 1) % MOD;
}

long long C(int n, int k) {
    if (k < 0 || k > n) return 0;
    return fac[n] % MOD * inv_fac[k] % MOD * inv_fac[n - k] % MOD;
}

long long catalan(int n) {
    // C_n = C(2n, n) / (n + 1)
    return C(2 * n, n) % MOD * power(n + 1, MOD - 2, MOD) % MOD;
}

// Alternative: C_n = C(2n, n) - C(2n, n+1) — no division needed
long long catalan_alt(int n) {
    return (C(2 * n, n) - C(2 * n, n + 1) + MOD) % MOD;
}

int main() {
    precompute_factorials();
    int n;
    cin >> n;
    cout << catalan(n) << "\n";
    return 0;
}

Complexity: O(N) precomputation, O(1) per query. This handles n up to 10⁶ comfortably within time and memory limits.

Handling Composite Moduli

If the modulus is composite, modular inverse may not exist. In this case, use one of:

The difference formula: C_n = C(2n, n) − C(2n, n+1). Compute binomial coefficients using Lucas' theorem or factorisation-based methods.
The O(n²) DP recurrence: avoids division entirely.
Legendre's formula: factor out primes from the numerator and denominator.

CP Applications

Counting Valid Bracket Sequences

Problem: Given n, count the number of valid sequences of n pairs of parentheses. Answer: C_n.

Generalisation: if we have multiple types of brackets (e.g., (), [], {}), the answer for k bracket types is kⁿ · C_n.

Number of BST Shapes

Problem: Given n distinct keys, how many structurally distinct BSTs can be formed? Answer: C_n.

// Count distinct BSTs for n keys
// Simply compute catalan(n) using the function above
int main() {
    precompute_factorials();
    int n;
    cin >> n;
    cout << catalan(n) << "\n";
}

Grid Paths Below Diagonal

Problem: Count lattice paths from (0, 0) to (n, n) using steps right (R) and up (U) that never go above the diagonal y = x. Answer: C_n.

More generally, paths from (0, 0) to (m, n) with m ≥ n that stay weakly below y = x is given by the ballot-style formula:

(m − n + 1) / (m + 1) · C(m + n, n)

Polygon Triangulation

Problem: In how many ways can a convex polygon with n + 2 vertices be triangulated? Answer: C_n.

Stack-Sortable Permutations

Problem: How many permutations of {1, …, n} can be sorted by passing through a single stack? Answer: C_n.

Recognition tip: Whenever a problem involves nested structures, balanced sequences, or recursive decompositions where you split into a "left part" and "right part" at every level, suspect Catalan numbers.

Generalizations

The ballot problem generalises Catalan numbers. The number of sequences of p copies of +1 and q copies of −1 (with p ≥ q) whose partial sums are always non-negative is:

(p − q + 1) / (p + 1) · C(p + q, q)

Setting p = q = n recovers C_n.

Super Catalan (Schröder) numbers and Motzkin numbers are related sequences that count paths with additional step types.

Catalan Number Modulo Identities

C_n is odd if and only if n = 2^k − 1 for some k.
Kummer's theorem can be used to find the exact power of a prime dividing C_n.
C_n mod 2 follows the pattern of the Sierpinski triangle.

Practice Problems

Balanced Brackets — Given n, output C_n mod 10⁹+7. (Direct application of the formula.)
Distinct BSTs (LeetCode 96) — Count the number of structurally unique BSTs that store values 1 to n.
Dyck Paths with Obstacles — Count Dyck paths of length 2n that avoid certain lattice points. (Requires inclusion-exclusion on top of Catalan.)
Polygon Triangulation Counting — Given a convex polygon with n vertices, count the number of triangulations.
CF 9D — How Many Trees? — Count binary trees with at most n vertices and height at most h.
CF 1830C — Hyperregular Bracket Strings — Counting bracket sequences with constraints, reducible to products of Catalan numbers.

Summary: Catalan numbers C_n = C(2n, n) / (n+1) count an enormous family of combinatorial objects. The closed-form with modular inverse handles most CP settings; fall back to the O(n²) recurrence when the modulus is composite. Learn the classic interpretations — they are your pattern-matching toolkit for recognising Catalan problems in contests.