Catalan Numbers: Complete Mathematical Guide

1. Introduction and Core Concepts

Catalan numbers form one of the most ubiquitous integer sequences in combinatorics and computer science. Defined for non-negative integers n, the nth Catalan number, denoted C_n or C(n), counts a surprisingly diverse set of structures. The sequence begins 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862, 16796, and grows asymptotically as approximately 4ⁿ / (n^3/2 * sqrt(pi)). Despite its simple definition, it appears in over 200 combinatorial interpretations cataloged by Richard Stanley.

Formally, Catalan numbers can be defined in several equivalent ways. The most common closed-form expression is C_n = (1 / (n + 1)) * binomial(2n, n) = (2n)! / ((n + 1)! * n!). An equally important definition is the recurrence relation: C₀ = 1 and C_n+1 = sum_i=0ⁿ C_i * C_n-i for n greater than or equal to 0. This recurrence reveals the self-similar, recursive nature that makes Catalan numbers so relevant to divide-and-conquer algorithms and recursive data structures.

Why do Catalan numbers matter for developers and algorithm designers? First, they provide a precise answer to fundamental counting problems: how many ways can you correctly match parentheses, triangulate a polygon, or construct a binary search tree? Second, they serve as a benchmark for combinatorial explosion. Understanding their growth helps engineers estimate the feasibility of brute-force enumeration, design efficient dynamic programming solutions, and analyze the complexity of parsing and optimization problems. If your system must enumerate all possible binary tree shapes, for example, knowing that C₂₀ is already 6,564,120,420 tells you immediately that exhaustive generation is infeasible. Finally, Catalan structures underpin core computer science concepts including stack-sortable permutations, context-free grammars, and non-crossing partitions used in databases and network routing.

Historical Context

The sequence is named after the Belgian mathematician Eugene Charles Catalan, who described them in 1838 while studying well-formed parentheses. However, they were previously discovered by Leonhard Euler in the 1750s in the context of polygon triangulation, and even earlier by the Chinese mathematician Antu Ming in the 1730s. This repeated independent discovery underscores their fundamental nature.

First Values and Intuition

To build intuition, consider small values. C₀ = 1 represents the empty structure. C₁ = 1 represents a single pair of parentheses "()". C₂ = 2 represents "(())" and "()()". C₃ = 5 represents the five ways to arrange three pairs of balanced parentheses. Each increment of n does not merely double the count; it multiplies it by roughly four, but with a damping factor of (n+1) in the denominator. This super-exponential yet sub-factorial growth places Catalan numbers in a unique complexity class that is critical to recognize during system design.

2. How It Works

The mechanism behind Catalan numbers is best understood through their three primary mathematical formulations: the recurrence relation, the closed-form binomial expression, and the generating function. Each formulation illuminates a different computational and combinatorial perspective.

The recurrence C_n+1 = sum_i=0ⁿ C_i * C_n-i captures the canonical decomposition pattern found in Catalan structures. For binary trees, it states that a tree with n+1 internal nodes consists of a root plus a left subtree with i nodes and a right subtree with n-i nodes. Summing over all possible splits i yields the total count. For well-formed parentheses, it corresponds to fixing the position of the matching closing parenthesis for the first opening parenthesis: if it closes after i+1 pairs inside, the remaining n-i pairs are outside. This convolution structure is why Catalan numbers appear whenever an object can be recursively decomposed into two smaller Catalan objects.

The closed form C_n = binomial(2n, n) / (n + 1) provides a direct computational route and a powerful analytic tool. The central binomial coefficient binomial(2n, n) counts all monotonic paths from (0,0) to (n,n) on a grid moving only right and up. Dividing by n+1 filters out only those paths that never cross above the diagonal — the Dyck paths. This is the essence of the reflection principle and Bertrand's ballot theorem. The formula also yields the elegant alternative C_n = binomial(2n, n) - binomial(2n, n+1), which shows Catalan numbers as the difference between total paths and bad paths that cross the diagonal.

The ordinary generating function C(x) = sum_{n greater than or equal to 0} C_n * xⁿ satisfies the quadratic equation C(x) = 1 + x * C(x)². Solving yields C(x) = (1 - sqrt(1 - 4x)) / (2x). This generating function is not just theoretical; it is the basis for deriving asymptotic approximations via singularity analysis and for solving related recurrences in algorithm analysis. Expanding sqrt(1 - 4x) with the binomial series directly produces the closed form. The singularity at x = 1/4 dictates the exponential growth factor of 4ⁿ.

Combinatorial Interpretations

The power of Catalan numbers lies in their many bijections. Every Catalan structure can be transformed into any other. Key interpretations include: number of Dyck words of length 2n (balanced parentheses), number of binary search trees with n distinct keys, number of ways to triangulate a convex polygon with n+2 sides, number of non-crossing partitions of a set of n elements, number of stack-sortable permutations of length n, and number of ways to connect 2n points on a circle with n non-intersecting chords. Recognizing which interpretation fits your problem is often the key to applying the correct dynamic programming optimization.

Growth and Asymptotics

Using Stirling's approximation, n! ~ sqrt(2 * pi * n) * (n/e)ⁿ, we obtain C_n ~ 4ⁿ / (n^3/2 * sqrt(pi)). This shows that Catalan numbers grow exponentially but with a polynomial damping factor. For practical purposes, C₁₅ = 9694845, C₁₉ = 1767263190 (exceeds 32-bit signed int), and C₃₅ ~ 3e19 (exceeds 64-bit). This rapid growth necessitates big integers or modulo arithmetic in most implementations.

3. Implementation

Computing Catalan numbers efficiently requires choosing the right algorithm for your constraints: value of n, need for exact versus modulo results, and time versus space trade-offs. Below are four canonical Python implementations, each suited to a different scenario.

The naive recursive implementation directly mirrors the definition but is exponentially slow due to repeated subproblems. Memoization transforms it into an efficient top-down dynamic programming solution. The bottom-up DP approach is often cleaner and avoids recursion depth limits. For large n where only a single value is needed, the binomial coefficient method using multiplicative formulas is optimal and avoids O(n²) work.

# Method 1: Top-down recursion with memoization
# Time: O(n^2), Space: O(n) for memo + recursion stack
def catalan_memo(n, memo=None):
    if memo is None:
        memo = {}
    # Base cases: C0 = 1, C1 = 1
    if n <= 1:
        return 1
    if n in memo:
        return memo[n]
    result = 0
    # Recurrence: C_n = sum_{i=0}^{n-1} C_i * C_{n-1-i}
    for i in range(n):
        result += catalan_memo(i, memo) * catalan_memo(n - 1 - i, memo)
    memo[n] = result
    return result

# Example usage
for i in range(8):
    print(f"C_{i} = {catalan_memo(i)}")

# Method 2: Bottom-up dynamic programming (tabulation)
# Preferred for interview settings: no recursion, predictable performance
def catalan_dp(n):
    if n <= 1:
        return 1
    # catalan[i] will hold C_i
    catalan = [0] * (n + 1)
    catalan[0] = 1
    catalan[1] = 1
    # Fill table iteratively
    for i in range(2, n + 1):
        # Compute C_i using previously computed values
        for j in range(i):
            catalan[i] += catalan[j] * catalan[i - 1 - j]
    return catalan[n]

def catalan_dp_all(n):
    # Return entire sequence up to n - useful for DP problems
    if n < 0:
        return []
    catalan = [0] * (n + 1)
    catalan[0] = 1
    if n >= 1:
        catalan[1] = 1
    for i in range(2, n + 1):
        for j in range(i):
            catalan[i] += catalan[j] * catalan[i - 1 - j]
    return catalan

print(catalan_dp_all(10))

import math

# Method 3: Closed form using binomial coefficient
# Time: O(n) with iterative multiplication, or O(n) with math.comb in Python 3.8+
# Space: O(1) extra, best for single large n
def catalan_binomial(n):
    # C_n = binom(2n, n) // (n + 1)
    if n <= 1:
        return 1
    # Python's math.comb is implemented in C and handles big ints efficiently
    return math.comb(2 * n, n) // (n + 1)

def catalan_binomial_iterative(n):
    # Avoids computing large factorials directly
    # Uses product formula: C_n = product_{k=2}^{n} (n + k) / k
    # Derived from binom(2n, n)/(n+1)
    if n <= 1:
        return 1
    result = 1
    for k in range(2, n + 1):
        # Multiply then divide to keep integer at each step
        result = result * (n + k) // k
    return result

def catalan_mod(n, mod=10**9 + 7):
    # For competitive programming: compute C_n modulo prime mod
    # Requires modular inverse of (n+1)
    if n <= 1:
        return 1
    # Compute binom(2n, n) mod mod using factorials and Fermat's little theorem
    # This is a simplified version assuming mod is prime and n < mod
    def mod_pow(a, e, m):
        res = 1
        while e > 0:
            if e & 1:
                res = (res * a) % m
            a = (a * a) % m
            e >>= 1
        return res

    numerator = 1
    denominator = 1
    # Compute (2n)! / (n! * n! * (n+1)) mod mod efficiently is more complex
    # For brevity, use math.comb then mod (only for n where comb fits in memory)
    return (math.comb(2 * n, n) // (n + 1)) % mod

# Method 4: Application - Generate all valid parentheses (count = Catalan number)
# Demonstrates constructive interpretation and backtracking
def generate_parentheses(n):
    # Generates all balanced parentheses strings of length 2n
    # Number of results is exactly C_n
    result = []
    def backtrack(current, open_count, close_count):
        # current: string built so far
        # open_count: number of '(' used
        # close_count: number of ')' used
        if len(current) == 2 * n:
            result.append(current)
            return
        # We can add '(' if we have not used all n
        if open_count < n:
            backtrack(current + "(", open_count + 1, close_count)
        # We can add ')' only if it would not make sequence invalid
        # i.e., more ')' than '(' would be invalid
        if close_count < open_count:
            backtrack(current + ")", open_count, close_count + 1)
    backtrack("", 0, 0)
    return result

def count_bst_structures(n):
    # Number of structurally unique BSTs with n distinct keys = C_n
    # This is why Catalan numbers appear in database index analysis
    return catalan_binomial(n)

# Demo
n = 3
parens = generate_parentheses(n)
print(f"n={n}, Catalan C_{n}={catalan_binomial(n)}, generated {len(parens)} structures")
print(parens)
# Output: ['((()))', '(()())', '(())()', '()(())', '()()()']

# Triangulation example: convex polygon with n+2 sides has C_n triangulations
def triangulations_count(sides):
    # sides >= 2, if sides < 3 return 0 or 1 depending on convention
    if sides < 3:
        return 0
    return catalan_binomial(sides - 2)

print(f"Hexagon (6 sides) triangulations: {triangulations_count(6)}")  # C_4 = 14

Together, these implementations cover most practical needs. For n less than 1000 and requiring the full sequence, use bottom-up DP. For a single large n up to 10⁶ with modulo, use the factorial precomputation with modular inverses. For exact big integers in Python, math.comb is surprisingly efficient due to its binary splitting implementation in C.

4. Step-by-Step Example

Let us walk through a complete concrete example: computing C₄ = 14 using both the recurrence and the closed form, and enumerating the corresponding structures for n=3 to make the abstract count tangible.

First, using the recurrence. We know C₀ = 1, C₁ = 1. Compute C₂ = C₀*C₁ + C₁*C₀ = 1*1 + 1*1 = 2. Next, C₃ = C₀*C₂ + C₁*C₁ + C₂*C₀ = 1*2 + 1*1 + 2*1 = 5. Now for C₄, we need all splits of 3: C₄ = C₀*C₃ + C₁*C₂ + C₂*C₁ + C₃*C₀ = 1*5 + 1*2 + 2*1 + 5*1 = 5 + 2 + 2 + 5 = 14. Notice the symmetry: the first and last terms are equal, as are the middle two. This symmetry can halve computation if exploited.

Now using the closed form: C₄ = binomial(8, 4) / 5. binomial(8,4) = 8! / (4! * 4!) = (40320) / (24 * 24) = 40320 / 576 = 70. Then 70 / 5 = 14. Alternatively, using the product formula: start with result=1, for k=2 to 4: k=2: result = 1 * (6)/2 = 3; k=3: result = 3 * (7)/3 = 7; k=4: result = 7 * (8)/4 = 14. Each step maintains integrality.

To connect the number to structures, enumerate n=3 (C₃=5). All balanced parentheses strings of length 6 are: 1) ((())) 2) (()()) 3) (())() 4) ()(()) 5) ()()(). Each corresponds bijectively to a binary tree with 3 nodes, a triangulation of a pentagon, and a Dyck path from (0,0) to (3,3) that never goes above the diagonal. For instance, ((())) corresponds to a degenerate tree where each node has only a left child (a chain), while ()()() corresponds to a degenerate tree leaning right. The mixed forms correspond to balanced trees.

Visualizing the Recurrence Tree

When computing C₄ via recursion, the call tree splits as follows: C₄ calls C₀*C₃, C₁*C₂, C₂*C₁, C₃*C₀. Each C₃ further splits into three subcalls, each C₂ into two. Without memoization, C₁ is computed 8 times and C₀ 14 times. With memoization, each C_i is computed exactly once, reducing the total number of distinct subproblems from exponential to linear in n, though the work to combine them remains O(n²).

Checking Correctness

A good sanity check for any implementation is to verify the first 10 values: 1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862. Also verify the recurrence for random n: compute C_n+1 both via the sum and via binomial formula and assert equality. For modulo implementations, test against known values modulo 1e9+7 for larger n, such as C₁₀₀ mod 1e9+7 = 558488487.

5. Complexity Analysis

Choosing an algorithm for Catalan numbers without understanding its complexity can lead to timeouts, stack overflows, or memory exhaustion. The complexity depends heavily on whether you need a single value or the entire sequence, whether you require exact big integers or modulo arithmetic, and the size of n.

Naive recursion without memoization has exponential time complexity approximately O(4ⁿ / n^3/2) because it recomputes the same subproblems many times, mirroring the growth of Catalan numbers themselves. Its space complexity is O(n) for the recursion stack, but time makes it unusable beyond n ~ 15.

Memoized recursion and bottom-up DP both achieve O(n²) time because they compute each C_i once, and computing C_i requires summing i terms. The total work is sum_i=0ⁿ i = O(n²). Space is O(n) to store the table. The bottom-up version has a smaller constant factor and avoids recursion overhead, making it preferable in production.

The binomial coefficient method is asymptotically faster. Computing binomial(2n, n) via the multiplicative product formula requires O(n) multiplications and divisions of big integers. However, the size of the integers themselves grows as O(n) bits, so the true bit-complexity is higher: naive multiplication of big integers costs O(M(n)) where M(n) is multiplication cost. In Python, using math.comb implemented in C with binary splitting yields O(n log n) time in practice and is the fastest for exact values up to several thousand. For modulo prime, precomputing factorials up to 2n allows O(n) preprocessing and O(1) per query after O(n) time.

* Binomial method's worst case includes big-integer multiplication cost; for n up to 10⁶ with modulo, it is linear. The DP methods are optimal when you need all values C₀..C_n. If you need only C_n for large n (e.g., n=5000), the binomial method is orders of magnitude faster. For n greater than 1000, O(n²) DP becomes prohibitive (1M operations for n=1000, 1B for n=31623), while O(n) remains feasible.

Space-Time Trade-offs

DP requires O(n) big integers, each of size O(n) bits, so total bit-space is O(n²). If memory is constrained and only the final value is needed, the iterative product uses O(1) auxiliary space. For modulo computations, all methods use O(1) or O(n) small integers, making them memory-efficient.

Best, Average, Worst Clarification

For Catalan computation, best, average, and worst cases are identical because the recurrence structure does not depend on input values — only on n. The distinction matters more for applications like counting BSTs where input distribution affects tree shape, but the count itself remains deterministic.

6. Variations and Optimizations

Beyond the basic algorithms, several variations optimize for specific constraints such as modulo arithmetic, large n, or related combinatorial families. Understanding these prevents reinventing inefficient solutions.

The most common optimization is modulo computation. In competitive programming and cryptography, you often need C_n mod p where p = 10⁹+7 (prime). Direct division by n+1 is not valid modulo p; you must multiply by the modular inverse of n+1. Precompute factorials fact[i] = i! mod p and inv_fact[i] = (i!)^-1 mod p for i up to 2n using Fermat's little theorem (a^p-1 = 1 mod p). Then C_n mod p = fact[2n] * inv_fact[n] % p * inv_fact[n] % p * inv(n+1) % p. This yields O(n) preprocessing and O(1) per query, enabling handling of up to n=10⁶ efficiently.

For very large n where n exceeds the modulus p, Lucas theorem and generalizations for Catalan numbers modulo prime powers are needed, as factorials contain factors of p and are not invertible. This leads to advanced techniques using Garner's algorithm and prime factorization of the binomial coefficient.

Another optimization is using the recurrence C_n+1 = C_n * 2*(2n+1) / (n+2). This linear recurrence allows computing the sequence iteratively in O(n) time with O(1) space per step, without the O(n²) convolution. Derivation: C_n+1/C_n = [ (2n+2)!/((n+2)!(n+1)! ) ] / [ (2n)!/((n+1)!n!) ] = (2n+2)(2n+1)/(n+2)(n+1) * (n+1)/1? Simplifying yields 2(2n+1)/(n+2). This is the fastest DP for generating the sequence sequentially and is numerically stable with big integers if you divide at each step.

Generalizations include Fuss-Catalan numbers (k-ary trees): C_n^(k) = 1/( (k-1)n +1 ) * binomial(k*n, n), counting k-ary trees. The Narayana numbers N(n,k) = 1/n * binomial(n,k) * binomial(n, k-1) refine Catalan numbers by counting Dyck paths with exactly k peaks, useful when you need distribution information, not just total count. The q-Catalan and Catalan's triangle extend the concept to weighted enumerations.

Memoization vs Tabulation Choice

Use memoization when n is large but you will query only a sparse subset of values, or when the recursion naturally prunes. Use tabulation when you need all values up to n or want to avoid recursion depth limits (Python recursion limit ~1000). For n greater than 1000, recursion will hit RecursionError unless you increase sys.setrecursionlimit.

Big Integer Handling

Python's int is arbitrary precision, so exact Catalan numbers for n=1000 (with ~600 digits) are computable, but printing or storing them is expensive. In languages like Java, use BigInteger; in C++, use boost::multiprecision::cpp_int. For n greater than 5000, consider using Python's decimal or logarithmic representation if only magnitude is needed.

7. Real-World Applications

While Catalan numbers originate in pure combinatorics, they have concrete applications in systems that developers build daily. Recognizing a Catalan structure allows you to apply known formulas, avoid brute force, and choose optimal data structures.

In compilers and parsers, the number of ways to parse an expression with n binary operators (e.g., a+b*c-d) under different parenthesizations is C_n. The number of possible abstract syntax trees for n+1 operands is Catalan. This directly impacts ambiguity in grammars: if a context-free grammar is ambiguous, the number of parse trees can be Catalan, leading to exponential parsing time for naive algorithms. Modern parser generators use this insight to enforce precedence and associativity.

In databases and search trees, the number of structurally unique binary search trees (BSTs) with n keys is C_n. This is crucial for analyzing the expected height of randomly built BSTs and for estimating the worst-case number of rotations needed to balance a tree. When a query optimizer enumerates join orders for n tables, the number of binary join trees is Catalan, which explains why optimizers use dynamic programming with pruning rather than exhaustive search beyond n ~ 10.

In networking and computational geometry, non-crossing partitions and triangulations are Catalan. Triangulating a convex polygon with n+2 sides (e.g., for mesh generation, computer graphics, or geographic information systems) has C_n possibilities. Finding the optimal triangulation (minimum weight) is a classic DP problem whose state space size is governed by Catalan numbers. Similarly, the number of ways to connect 2n points on a circle with non-intersecting chords — modeling RNA secondary structure prediction or non-crossing network connections — is C_n.

In operating systems and concurrency, Dyck paths model stack behavior. The sequence of pushes and pops that never underflows a stack of size n corresponds to a Dyck word. Counting valid interleavings of n pushes and n pops is Catalan, which helps analyze deadlock-free resource allocation and the number of ways to correctly match parentheses in code editors.

Even in web servers, Catalan numbers appear indirectly: the number of ways to correctly nest n asynchronous callbacks or to match n opening and closing HTML tags without crossing is Catalan. Understanding this helps when designing validators for well-formed markup or when analyzing the complexity of bracket matching in code linters.

8. Comparison with Alternatives

Catalan numbers are often confused with other combinatorial sequences. Choosing the wrong model leads to incorrect counts and flawed capacity planning. This section contrasts Catalan numbers with related sequences and with alternative computation strategies.

Compared to factorials (n!), Catalan numbers grow much slower: n! ~ (n/e)ⁿ while C_n ~ 4ⁿ / n^3/2. Factorials count permutations (ordered arrangements), whereas Catalan counts constrained structures (non-crossing, balanced). Bell numbers B_n count all partitions of a set (allowing crossing), growing even faster than Catalan but slower than n! for moderate n. Stirling numbers of the second kind S(n,k) count partitions into exactly k blocks, refining Bell numbers. Central binomial coefficients binomial(2n, n) are larger than Catalan by factor n+1 and count unrestricted paths.

For computation, the alternatives are DP versus closed form versus generating functions. DP is intuitive and yields all intermediate values but is O(n²). Closed form is O(n) but requires handling division and big integers. For modulo arithmetic, factorial precomputation is the standard alternative to DP, offering O(1) queries after O(n) setup.

When deciding which sequence models your problem, ask: does order matter? If yes, factorial. Does the structure require non-crossing or nesting? If yes, Catalan. Is any partition allowed? Bell/Stirling. This checklist prevents overcounting. For example, counting ways to partition n database records into any number of shards is Bell, but counting ways to parenthesize n joins without crossing is Catalan.

Computation Method Comparison

If you need only one Catalan number modulo prime, factorial precomputation wins. If you need the entire sequence for DP (e.g., optimal binary search tree), bottom-up DP is simpler and already gives you all values. If n is greater than 5000 and you need exact integer, use math.comb with Python's big ints; avoid O(n²) DP which would require 25 million big-int multiplications.

9. Common Mistakes and Best Practices

Even experienced developers make subtle errors when implementing Catalan-related logic. The most frequent pitfalls involve off-by-one errors, integer overflow, recursion limits, and misapplying the formula.

Off-by-one is the classic mistake. C_n counts structures with n pairs, n nodes, or n+2 polygon sides depending on context. Confusing n and n+1 leads to using C_n-1 instead of C_n. For example, the number of BSTs with n nodes is C_n, but the number of triangulations of an n-gon is C_n-2. Always verify with small n: a triangle (3 sides) has 1 triangulation, which is C₁=1, not C₃=5. Document whether your function parameter represents pairs, nodes, or sides.

Integer overflow is pervasive in languages with fixed-width integers. C₁₉ exceeds 2³¹-1, C₃₅ exceeds 2⁶³-1. In Java, int overflows at n=19; in C++ 64-bit, at n=35. Use big integers or modulo arithmetic and explicitly check bounds. In Python, big ints hide overflow but cause performance degradation for large n due to huge digit arrays; consider modulo if exact value is not needed.

Recursion depth and repeated computation trap many interview solutions. A naive recursive function without memoization will time out for n greater than 20 and cause exponential stack growth. Even with memoization, Python's recursion limit (~1000) will be exceeded for n greater than 1000. Prefer iterative DP or increase recursion limit via sys.setrecursionlimit, but iterative is safer for production.

Incorrect modular division is another common error. Writing (binom(2n,n) // (n+1)) % mod is wrong when working modulo prime because integer division before modulo loses information. You must compute modular inverse: binom % mod * inv(n+1) % mod. Use pow(n+1, mod-2, mod) in Python for prime mod.

• Best Practice 1: Validate with known small values. Always test C₀..C₅ = 1,1,2,5,14,42.
• Best Practice 2: Use the linear recurrence C_n+1 = C_n * 2*(2n+1)//(n+2) for sequential generation — O(n) time, O(1) space, integer-safe if you divide after multiplying.
• Best Practice 3: For DP counting problems (e.g., counting BSTs), store Catalan numbers in a table and reuse them; do not recompute via binom each time.
• Best Practice 4: When n is large (greater than 1000) and you need exact value, use math.comb or iterative product to avoid O(n²) DP.
• Best Practice 5: Document the combinatorial interpretation. A function named count_bsts(n) should clearly state it returns C_n and reference the mapping.
• Best Practice 6: For modulo problems, precompute factorials and inverse factorials once up to 2*max_n, not per query.

Finally, avoid floating-point approximations for exact counts. Using Stirling's approximation or floating division sqrt(1-4x) will introduce rounding errors for n greater than 20. Stick to integer arithmetic for exact results and use logarithms only for magnitude estimation.

10. Interview Questions

Catalan numbers are a favorite in technical interviews because they test recursion, dynamic programming, combinatorics, and the ability to recognize hidden structure. Below are common questions with solution sketches.

Question 1: Number of Unique BSTs (LeetCode 96)

Given n distinct keys (1..n), how many structurally unique BSTs can be formed? This is exactly C_n. The optimal solution uses DP: dp[0]=1, dp[n]= sum_i=0^n-1 dp[i]*dp[n-1-i]. Explain why: choose root i+1, left subtree has i nodes, right has n-1-i nodes. Complexity O(n²) time, O(n) space. Follow-up: generate all trees (LeetCode 95) — count is Catalan, generation is backtracking. Be ready to derive the recurrence and discuss overflow for n greater than 19.

Question 2: Valid Parentheses Generation and Counting

Given n pairs of parentheses, generate all combinations of well-formed parentheses. How many are there? Count is C_n. Generation uses backtracking with constraints open less than n and close less than open. Counting can be done via DP or binomial. Interviewers often ask to prove the count is Catalan via the reflection principle or to compute it modulo 1e9+7 for large n. Emphasize the bijection to Dyck paths and the O(4ⁿ/sqrt(n)) output size — generating all is exponential, so counting is preferred for large n.

Question 3: Polygon Triangulation and Matrix Chain Multiplication

How many ways can a convex polygon with n+2 sides be triangulated? How many ways to parenthesize n matrices? Both are C_n. For triangulation, pick a base edge and choose a third vertex to form a triangle, splitting polygon into two smaller polygons with i+1 and n-i+1 sides. This yields the Catalan recurrence. For matrix chain, the number of full parenthesizations of n+1 matrices is C_n. The follow-up optimization problem — finding minimum multiplication cost — is classic DP with O(n³) time, where Catalan counts the search space.

Question 4: Compute nth Catalan Number Efficiently

Write a function to compute C_n for n up to 1000. Handle large numbers and discuss complexity. Expected answer: present both O(n²) DP and O(n) binomial methods, discuss big integers, and provide modulo variant. A strong candidate will mention the linear recurrence C_n+1 = C_n * 2*(2n+1)/(n+2) for O(n) sequential generation, and will note that naive recursion is exponential and unacceptable. They will also discuss space optimization and Python's math.comb.

Question 5: Stack-Sortable Permutations and Dyck Paths

How many permutations of length n can be sorted by a single stack? How many monotonic paths from (0,0) to (n,n) never go above diagonal? Both are C_n.