Catalan Numbers

Why Catalan Numbers Matters

With three pairs of parentheses, how many correctly balanced strings can you write? There are five: ((())), (()()), (())(), ()(()), and ()()(). Choosing arbitrary positions for the three opening parentheses would give 20 strings, but many close a pair before opening it. Catalan numbers count the arrangements that obey this nesting rule.

The same sequence counts several other structures: binary search tree shapes on a fixed set of ordered keys, full binary tree shapes, noncrossing pairings, polygon triangulations, and ways to fully parenthesize an expression. Their connection is a common recursive pattern: choose a split, independently choose a left structure and a right structure, then combine them.

This lesson turns that pattern into dynamic programming. You will derive the recurrence from the first matching parenthesis, trace its products and running totals, implement it in three languages, and recognize when an apparent Catalan problem needs a different size parameter or additional constraints.

Core Concepts and Terminology

The input is a nonnegative integer n. The nth Catalan number C(n) counts balanced parenthesis strings with n pairs. Each string contains n opening and n closing parentheses. In every prefix, the number of opening parentheses is at least the number of closing parentheses; at the end, the two counts are equal. The balance of a prefix is its opening count minus its closing count.

The sequence begins 1, 1, 2, 5, 14, 42, 132, 429 for n = 0 through 7. The value C(0) = 1 represents the one empty string. It is the multiplicative identity needed when one side of a recursive split is empty.

Every nonempty balanced string has a unique decomposition ( + A + ) + B. The closing parenthesis shown is the match for the first opening parenthesis. If A contains i pairs, B contains n − 1 − i pairs. The outer matched pair uses the remaining one pair. For each fixed i, there are C(i) choices for A and C(n − 1 − i) choices for B, giving their product. Different i values describe disjoint cases, so we add those products.

A Dyck path draws the same structure: read ( as a step up and ) as a step down, moving one unit right each time. A balanced string becomes a path from (0, 0) to (2n, 0) that never goes below height zero. The first return to zero identifies the matching parenthesis used in the decomposition.

How Catalan Numbers Works, Step by Step

Allocate an array dp with n + 1 entries, initially zero, and set dp[0] = 1. Process sizes s in increasing order from 1 through n. For each size, start total = 0, then try every left size i from 0 through s − 1. Set right = s − 1 − i and add dp[i] × dp[right] to total. After all splits have been processed, store total in dp[s].

Both referenced sizes are smaller than s. Their entries are therefore complete before we start computing dp[s]. There is no need for recursive calls or an extra table dimension. The outer loop orders the subproblems; the inner loop combines every possible split of the current problem.

For example, when computing C(3), dp already begins [1, 1, 2]. The first split contributes C(0) × C(2) = 2. The next split contributes C(1) × C(1) = 1, increasing total from 2 to 3. The last split contributes C(2) × C(0) = 2, so dp[3] becomes 5.

The implementations below reduce each product and running total modulo M = 1,000,000,007. This changes the stored numbers when counts become large, but it preserves the recurrence modulo M. No division or modular inverse is used.

flowchart TD
    A["Read nonnegative n"] --> B{"n negative?"}
    B -->|Yes| X["Reject input"]
    B -->|No| C["Allocate dp[0..n]; dp[0] = 1; s = 1"]
    C --> D{"s at most n?"}
    D -->|No| R["Return dp[0..n]"]
    D -->|Yes| E["total = 0; i = 0"]
    E --> F{"i less than s?"}
    F -->|Yes| G["right = s - 1 - i"]
    G --> H["term = dp[i] times dp[right] mod M"]
    H --> I["total = (total + term) mod M"]
    I --> J["i = i + 1"]
    J --> F
    F -->|No| K["dp[s] = total; s = s + 1"]
    K --> D

Worked Example with a Full Trace

Compute the Catalan prefix through n = 4. Initialize dp = [1, 0, 0, 0, 0]. The following trace records all ten product terms and every intermediate total.

1. Size s = 1: start total = 0. For i = 0, right = 0, so add 1 × 1 = 1; total becomes 1. Store dp[1] = 1, giving [1, 1, 0, 0, 0].
2. Size s = 2: reset total = 0. For i = 0, right = 1, add 1 × 1 = 1; total becomes 1. For i = 1, right = 0, add 1 × 1 = 1; total becomes 2. Store dp[2] = 2, giving [1, 1, 2, 0, 0].
3. Size s = 3: reset total = 0. For i = 0, right = 2, add 1 × 2 = 2; total becomes 2. For i = 1, right = 1, add 1 × 1 = 1; total becomes 3. For i = 2, right = 0, add 2 × 1 = 2; total becomes 5. Store dp[3] = 5, giving [1, 1, 2, 5, 0].
4. Size s = 4: reset total = 0. For i = 0, right = 3, add 1 × 5 = 5; total becomes 5. For i = 1, right = 2, add 1 × 2 = 2; total becomes 7. For i = 2, right = 1, add 2 × 1 = 2; total becomes 9. For i = 3, right = 0, add 5 × 1 = 5; total becomes 14. Store dp[4] = 14, giving [1, 1, 2, 5, 14].

For size four, the split cases are 0 + 3, 1 + 2, 2 + 1, and 3 + 0 pairs inside A and B. Their counts are 5, 2, 2, and 5. Each complete string has exactly one first matching pair, so the four cases never overlap.

As an independent arithmetic check, C(4) = binomial(8, 4)/(4 + 1) = 70/5 = 14. The closed form will be discussed below; the DP itself requires no division.

Implementation in Python, C++, and Java

Each program computes the table from C(0) through C(20) once, then prints the same selected entries. The implementation is the quadratic split recurrence, with explicit modulus M = 1,000,000,007. Stored values are Catalan numbers modulo M. They equal the full counts for the small entries shown through C(10), but the C(20) line is a remainder.

Python uses built-in arbitrary-precision integers. C++ uses long long: both multiplicands are at most M − 1, so their product is at most (M − 1)² = 1,000,000,012,000,000,036, safely below the signed 64-bit maximum. It reduces the product before adding it to total. Java uses BigInteger for products, sums, and remainders. The fixed modulus is part of this safety argument; changing it requires checking the C++ product bound again.

All versions reject negative n. Array allocation and running time also limit feasible n: quadratic DP is intended for moderate input sizes, not arbitrarily large indices. The Java allocation uses checked addition for n + 1.

MOD = 1_000_000_007


def catalan_table(n: int) -> list[int]:
    if n < 0:
        raise ValueError("n must be nonnegative")
    dp = [0] * (n + 1)
    dp[0] = 1
    for size in range(1, n + 1):
        total = 0
        for left in range(size):
            right = size - 1 - left
            term = (dp[left] * dp[right]) % MOD
            total = (total + term) % MOD
        dp[size] = total
    return dp


def main() -> None:
    samples = [0, 1, 2, 3, 4, 5, 10, 20]
    dp = catalan_table(max(samples))
    print(f"modulus = {MOD}")
    for n in samples:
        print(f"C({n}) = {dp[n]}")


if __name__ == "__main__":
    main()

#include <algorithm>
#include <cstddef>
#include <iostream>
#include <stdexcept>
#include <vector>

constexpr long long MOD = 1'000'000'007LL;

std::vector<long long> catalan_table(int n) {
    if (n < 0) {
        throw std::invalid_argument("n must be nonnegative");
    }
    std::vector<long long> dp(static_cast<std::size_t>(n) + 1, 0);
    dp[0] = 1;
    for (std::size_t size = 1; size < dp.size(); ++size) {
        long long total = 0;
        for (std::size_t left = 0; left < size; ++left) {
            const std::size_t right = size - 1 - left;
            const long long term = (dp[left] * dp[right]) % MOD;
            total = (total + term) % MOD;
        }
        dp[size] = total;
    }
    return dp;
}

int main() {
    const std::vector<int> samples = {0, 1, 2, 3, 4, 5, 10, 20};
    const int maximum = *std::max_element(samples.begin(), samples.end());
    const std::vector<long long> dp = catalan_table(maximum);
    std::cout << "modulus = " << MOD << '\n';
    for (int n : samples) {
        std::cout << "C(" << n << ") = " << dp[n] << '\n';
    }
}

import java.math.BigInteger;
import java.util.Arrays;

public class Main {
    private static final BigInteger MOD = BigInteger.valueOf(1_000_000_007L);

    public static BigInteger[] catalanTable(int n) {
        if (n < 0) {
            throw new IllegalArgumentException("n must be nonnegative");
        }
        BigInteger[] dp = new BigInteger[Math.addExact(n, 1)];
        Arrays.fill(dp, BigInteger.ZERO);
        dp[0] = BigInteger.ONE;
        for (int size = 1; size < dp.length; ++size) {
            BigInteger total = BigInteger.ZERO;
            for (int left = 0; left < size; ++left) {
                int right = size - 1 - left;
                BigInteger term = dp[left].multiply(dp[right]).mod(MOD);
                total = total.add(term).mod(MOD);
            }
            dp[size] = total;
        }
        return dp;
    }

    public static void main(String[] args) {
        int[] samples = {0, 1, 2, 3, 4, 5, 10, 20};
        int maximum = 0;
        for (int n : samples) {
            maximum = Math.max(maximum, n);
        }
        BigInteger[] dp = catalanTable(maximum);
        System.out.println("modulus = " + MOD);
        for (int n : samples) {
            System.out.println("C(" + n + ") = " + dp[n]);
        }
    }
}

Run Python with Python 3.9 or later. Compile C++ with C++14 or later. Save Java as Main.java, compile with javac Main.java, and run with java Main. Each program prints the following nine lines:

• modulus = 1000000007
• C(0) = 1
• C(1) = 1
• C(2) = 2
• C(3) = 5
• C(4) = 14
• C(5) = 42
• C(10) = 16796
• C(20) = 564120378

The full value C(20) is 6,564,120,420. Reducing it modulo 1,000,000,007 gives 564,120,378, matching the programs. To obtain full counts, remove modular reductions in Python or Java while retaining arbitrary-precision integers. C++ then needs arbitrary-precision arithmetic or a proven bound on every product and sum; removing % MOD alone does not make the program an exact unbounded counter.

Complexity, Correctness, and Invariants

For n ≥ 1, the outer loop computes sizes 1 through n, and size s tries exactly s splits. The total number of product terms is 1 + 2 + … + n = n(n + 1)/2. Thus the fixed-modulus DP takes Θ(n²) time and Θ(n + 1) working storage, including its returned table. It uses only O(1) additional bounded-size state beyond that table. For n = 0, time and storage are Θ(1).

For a fixed n, best, average, and worst cases have the same loop count: there are no data-dependent choices or early exits in the recurrence. Negative inputs are rejected before allocation. These are unit-cost arithmetic bounds for the fixed modulus. For full counts, Catalan values have Θ(n) bits as n grows, so multiplication and addition are no longer constant-time operations; the exact bit complexity depends on the integer arithmetic algorithms used.

Correctness follows by induction on the computed size. Initially dp[0] = 1 correctly counts the empty structure. Assume every dp[j] with j less than s is correct modulo M. For each left size i, the unique decomposition ( + A + ) + B gives a bijection between size-s structures with that split and pairs of structures counted by dp[i] and dp[s − 1 − i]. Multiplication counts all pairs, and addition combines disjoint split cases. Therefore the completed total is C(s) modulo M, establishing the induction step.

The inner-loop invariant is equally useful when debugging: before processing left size i, total is the sum of all product terms for left sizes 0 through i − 1, modulo M. Completed smaller dp entries remain unchanged. When i reaches s, every split has been included exactly once, so storing total in dp[s] is correct.

The multiplicative recurrence is C(s + 1) = C(s) × 2(2s + 1)/(s + 2), starting from C(0) = 1. Every stage gives an integer when the multiplication is performed before the division. It is often preferable when the goal is simply to compute full Catalan values; the quadratic DP exposes the decomposition and adapts naturally to many constrained variants.

The table counts arithmetic stages rather than bit operations. “O(1) big-integer objects” does not mean constant bytes: the integers themselves grow. If a method returns every value through n rather than streaming them, retaining that output also requires n + 1 entries.

Variants, Pitfalls, and Optimizations

Keep the empty structure. Set C(0) = 1, not zero. A split with an empty left side still has one possible empty left choice. Multiplying by zero would incorrectly remove every structure whose decomposition contains an empty part, and the recurrence would produce zeros throughout.

Check what n measures. Balanced parentheses use n pairs, while ordinary binary search tree shapes use n nodes with distinct keys in a fixed sorted order. Full ordered binary trees use n internal nodes and therefore have n + 1 leaves and 2n + 1 total nodes. Fully parenthesizing m operands gives C(m − 1) possibilities. Triangulating a convex m-gon gives C(m − 2) possibilities. These are related structures, but their size conventions differ.

Preserve left/right order. For tree shapes and parenthesizations, the left and right parts occupy different positions. Mirroring can create a different structure. Although C(i) × C(s − 1 − i) equals its mirrored term numerically, both split positions must normally be counted. You may optimize a symmetric sum by doubling matched terms and including the middle term once, but that reduces only the constant factor; it remains quadratic overall.

Do not divide modular residues as ordinary integers. The closed form C(n) = binomial(2n, n)/(n + 1) is an exact integer identity. After taking a remainder, ordinary division by n + 1 is generally invalid. Modular division requires an inverse and proof that it exists. The supplied DP avoids this issue and works for composite moduli as well, subject to suitable arithmetic bounds. Another integer identity, C(n) = binomial(2n, n) − binomial(2n, n + 1), follows from reflecting paths that first cross below zero.

Additional constraints usually change the state. If balanced strings have a maximum allowed nesting depth, a position-and-balance DP is a more direct model. If the problem asks to list strings rather than count them, backtracking must emit every valid output, so a fast counting formula does not remove the cost of generation. Catalan growth is approximately 4ⁿ divided by the product of sqrt(pi) and n to the power 3/2, which explains how quickly listing becomes expensive.

Practice Problems and Real-World Use

To recognize a Catalan model, search for a unique separator or root that divides an object into an ordered pair of smaller objects. Then identify the size used by that separator. Prove the decomposition works in both directions: every valid object gives one split, and every allowed pair of smaller objects produces a valid larger object.

The same counts help measure a search space even when the ultimate task is optimization or generation. For example, Catalan numbers count matrix-chain parenthesizations, while the standard matrix-chain cost DP chooses the cheapest grouping using matrix dimensions. Those are different outputs, and the counting recurrence does not by itself solve the optimization problem.

In the full-tree row, “ordered” means that left and right child positions are distinguished. Every internal node has exactly two children. In the expression and matrix-chain examples, the operand or matrix order stays fixed. In the polygon example, the vertices are fixed and the polygon is convex; arbitrary polygon geometry can change which diagonals are permitted.

For an additional exercise, count the possible output permutations from a fixed increasing input passed through one stack, with each item pushed and popped once. The answer is C(n), and the legal push/pop sequences correspond to balanced parentheses. This uses one stack and a fixed input order; changing the machine changes the counting problem.

Verify small values by independently enumerating balanced strings and rejecting any prefix with negative balance. Compare the DP against binomial(2n, n)/(n + 1) for a range of indices using exact integer arithmetic, then reduce modulo M for comparison with the programs. Include n = 0, negative-input rejection, C(4) = 14, and a value such as C(20) that exceeds M, so indexing, base cases, arithmetic, and output interpretation are all exercised.