Catalan Numbers

The Catalan numbers 1, 1, 2, 5, 14, 42, 132, 429, ... count a surprising number of structures: balanced parenthesis strings, binary tree shapes, non-crossing pairings, triangulations, lattice paths that never cross the diagonal. Recognizing the pattern turns a scary counting question into a known O(n^2) DP or an O(n) formula.

Intuition

All Catalan structures share one recursive shape: split at a distinguished point into two independent smaller structures whose sizes add up to n - 1.

• Binary trees with n nodes: pick the root; the left subtree has i nodes and the right one n - 1 - i.
• Balanced strings with n pairs: the first ( is matched by some ); inside that pair there are i pairs, after it n - 1 - i pairs.
• Non-crossing handshakes among 2n people at a round table: person 1 shakes hands with someone, splitting the others into two independent groups.

So C(0) = 1 and C(n) = sum over i from 0 to n-1 of C(i) * C(n - 1 - i). The closed form is C(n) = binom(2n, n) / (n + 1), and consecutive terms satisfy C(n) = C(n - 1) * 2(2n - 1) / (n + 1).

Why the closed form holds (reflection principle). A balanced string is a path of n up-steps and n down-steps that never goes below zero. There are binom(2n, n) paths in total. Take a bad path and reflect everything after its first visit to -1; this turns it into a path with n + 1 down-steps and n - 1 up-steps, and the map is a bijection. So the bad paths number binom(2n, n + 1), and the good ones binom(2n, n) - binom(2n, n + 1) = binom(2n, n) / (n + 1). The same argument with a openers and b <= a closers gives the ballot count binom(a + b, b) - binom(a + b, b - 1).

When to use it in interviews / OAs

• "How many structurally different BSTs/binary trees with n nodes?"
• Counting balanced bracket strings, valid stack push/pop orders, non-crossing matchings or triangulations.
• A DP whose recurrence splits a size-n problem into sizes i and n - 1 - i and multiplies.
• Compute the first few values by brute force; if you see 1, 2, 5, 14, 42, it is Catalan.

Template

from math import comb


def catalan_table(n: int) -> list[int]:
    # C[i] = number of binary tree shapes with i nodes: choose the left subtree size j
    C = [1] + [0] * n
    for i in range(1, n + 1):
        C[i] = sum(C[j] * C[i - 1 - j] for j in range(i))
    return C


def catalan(n: int) -> int:
    # exact value via C(k) = C(k - 1) * 2(2k - 1) / (k + 1); the division is always exact
    c = 1
    for k in range(1, n + 1):
        c = c * 2 * (2 * k - 1) // (k + 1)
    return c


def catalan_mod(n: int, p: int = 10**9 + 7) -> int:
    # binom(2n, n) / (n + 1) modulo a prime p > 2n
    num = den = 1
    for i in range(1, n + 1):
        num = num * (n + i) % p  # builds (2n)! / n!
        den = den * i % p  # builds n!
    den = den * (n + 1) % p
    return num * pow(den, p - 2, p) % p


def ballot(a: int, b: int) -> int:
    # strings of a "(" and b ")" whose running balance never drops below zero
    if b > a:
        return 0
    return comb(a + b, b) - (comb(a + b, b - 1) if b else 0)  # reflection principle

The O(n^2) table is what you would derive live in an interview ("unique BSTs": choose the root, multiply the counts of the two sides). The closed form is the follow-up.

Generating instead of counting

When the question asks for the structures themselves, the output has Catalan size, so plain backtracking is optimal. For balanced parentheses: open while openers remain, close only when it keeps the string valid.

def generate_parentheses(n: int) -> list[str]:
    out, cur = [], []

    def build(opened: int, closed: int) -> None:
        if len(cur) == 2 * n:
            out.append("".join(cur))
            return
        if opened < n:  # an opener is still available
            cur.append("(")
            build(opened + 1, closed)
            cur.pop()
        if closed < opened:  # only close what is open
            cur.append(")")
            build(opened, closed + 1)
            cur.pop()

    build(0, 0)
    return out

Complexity

The DP table is O(n^2) time and O(n) space. The ratio formula is O(n) big-integer steps; the modular version is O(n + log p). Generating all structures costs O(C(n) * n), and C(n) grows like 4^n / (n^1.5 * sqrt(pi)), so generation is only feasible for n up to about 15.

Common pitfalls

• Off-by-one in the index: n pairs of parentheses give C(n); a convex polygon with n + 2 sides has C(n) triangulations; 2n people give C(n) handshake patterns; n leaves of a full binary tree give C(n - 1) shapes.
• Overflow: C(35) still fits in a signed 64-bit integer, C(36) does not. Use the modular formula (or Python integers).
• Division in modular arithmetic: /(n + 1) becomes a modular inverse and requires a prime modulus larger than 2n.
• Not every split recurrence is Catalan: if the two sides are not independent, or the split point has weights, you need a general interval DP.
• Odd sizes: an odd number of people cannot all shake hands; full binary trees need an odd number of nodes.

Interview variations

• Unique binary search trees (count) and unique BSTs II (generate every tree).
• Generate parentheses, check valid push/pop sequences of a stack.
• Handshakes that do not cross around a round table.
• All possible full binary trees with n nodes (n odd): C((n - 1) / 2) shapes.
• Lattice paths below the diagonal, mountain ranges, balanced sequences with a opens and b closes: ballot numbers.
• Number of ways to triangulate a convex polygon (with weights it becomes interval DP).