vault

Catalan Numbers

22 min read

Catalan Numbers

The Catalan numbers are the integer sequence C₀ = 1, C₁ = 1, C₂ = 2, C₃ = 5, C₄ = 14, C₅ = 42, C₆ = 132, … (OEIS A000108) that counts an astonishing variety of combinatorial structures — Richard Stanley’s Catalan Numbers monograph (Cambridge, 2015) catalogs 214 distinct combinatorial interpretations of Cₙ, and Enumerative Combinatorics Vol. 2 Exercise 6.19 enumerates 66 of them with proofs. The closed form Cₙ = C(2n, n) / (n+1) and the recurrence C_{n+1} = Σ_{i=0}^{n} Cᵢ · C_{n-i} appear as solutions to dozens of problems that, on the surface, have nothing to do with each other: balanced parenthesizations of n pairs, structurally distinct binary trees with n internal nodes, triangulations of an (n+2)-gon, lattice paths from (0, 0) to (n, n) not crossing the diagonal (Dyck paths), valid permutations of n items through a single stack, non-crossing partitions of 2n points on a circle, mountain ranges with n upstrokes and n downstrokes, and the number of ways n+1 non-associative factors can be parenthesized. The number is named for Belgian mathematician Eugène Catalan (1838), who introduced the recurrence in studying parenthesizations, but earlier instances trace back to Johann Andreas Segner (1758), Leonhard Euler in his correspondence with Goldbach, and even Mongolian-Chinese mathematician Antu Ming in the early 18th century. This note develops the closed form via the reflection principle, gives both the recurrence and a generating-function proof, traces concrete examples for n = 3, 4 across three different interpretations to make the bijections concrete, presents the modular-arithmetic computation idiom for Cₙ mod p, and surveys the most important interpretations for interview problems.

1. The Sequence and Its Two Defining Formulas

n   :  0   1   2   3   4    5    6     7      8      9       10
C_n :  1   1   2   5  14   42  132   429   1430   4862    16796

Closed form:

Cₙ = C(2n, n) / (n + 1) = (2n)! / ((n+1)! · n!)

Recurrence:

C_{n+1} = Σ_{i=0}^{n} Cᵢ · C_{n-i}        with  C₀ = 1

Both formulas produce the same sequence — the closed form is preferable for direct computation, the recurrence for combinatorial proofs and connection to other sequences. We will derive the closed form in §4 via the reflection principle (Désiré André’s argument from 1887, applied to lattice paths) and the recurrence via “first return to the diagonal” decomposition in §5.

Asymptotic growth: Cₙ ~ 4ⁿ / (n^(3/2) · √π). So Cₙ grows roughly like 4ⁿ divided by n^(3/2) — exponential growth, slightly tempered. For n = 30, Cₙ ≈ 3.8 · 10^15. For n = 50, Cₙ ≈ 1.98 · 10^28 — far beyond 64-bit integers, so modular computation is essential for large n.

2. Tiny Worked Example — C₃ = 5 Across Three Interpretations

C₃ = 5. Let’s see five different objects in each of three different “Catalan worlds.”

2.1 Balanced Parentheses with 3 Pairs

The 5 distinct ways to balance 3 pairs of parentheses:

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

Each is a valid string of 3 left-parens and 3 right-parens such that no prefix has more right-parens than left.

2.2 Binary Trees with 3 Internal Nodes (4 Leaves)

The 5 structurally distinct full binary trees with 3 internal nodes (where every internal node has exactly two children, and we count leaves but not labels):

   *           *           *           *           *
  / \         / \         / \         / \         / \
 *   L       *   L       L   *       L   *       *   *
/ \         / \             / \         / \      / \  / \
* L         L *             * L         L *      L L  L L
/\          / \             / \         / \
L L         L L             L L         L L

(Here * is an internal node, L is a leaf.) These are the 5 shapes. Each is a “binary tree” in the sense relevant to expression parsing.

2.3 Triangulations of a Regular Pentagon

A pentagon (5 vertices) can be triangulated by adding non-crossing chords. Number of triangulations: C₃ = 5. The triangulations are characterized by which vertex serves as a “fan apex”:

Pentagon vertices labeled 1, 2, 3, 4, 5.
Triangulations (each lists the diagonals added):
1. (1-3), (1-4)        ← fan from vertex 1
2. (2-4), (2-5)        ← fan from vertex 2
3. (3-5), (1-3)        ← fan from vertex 3
4. (1-4), (2-4)        ← fan from vertex 4
5. (2-5), (3-5)        ← fan from vertex 5

The bijection from balanced parens to triangulations: each pair of matching parens corresponds to a triangle in the triangulation. Stanley’s Catalan Numbers §1.5 gives an explicit bijection.

The remarkable fact is that all three sets — strings, trees, polygons — have exactly the same count, 5, because they are in bijection. A balanced-paren string ↔ a binary tree (treat each ( as a left child descent, each matching ) as a return) ↔ a polygon triangulation (slice off a triangle for each pair of parens). These bijections are not coincidence; they all come from the underlying combinatorial structure that Catalan numbers count.

3. The Catalan Recurrence — From “First Return”

The recurrence C_{n+1} = Σ Cᵢ · C_{n-i} has a beautiful combinatorial proof, easiest to state for balanced parentheses.

A balanced-paren string of n + 1 pairs starts with (. Find the matching ) of this opening paren. The string decomposes uniquely as

(  X  )  Y

where X is a balanced-paren string of i pairs (the contents of the leading parens) and Y is a balanced-paren string of n - i pairs (the rest), with 0 ≤ i ≤ n. By the multiplication principle:

(strings with n+1 pairs)
  = Σ_{i=0}^{n} (strings X with i pairs) · (strings Y with n-i pairs)
  = Σ_{i=0}^{n} Cᵢ · C_{n-i}

Hence C_{n+1} = Σ Cᵢ · C_{n-i}. ✓

This pattern — decompose at the first return to the baseline — recurs in many Catalan-counted structures. For Dyck paths, the first return to the x-axis splits the path into two smaller Dyck-like pieces. For binary trees, the root’s left subtree has i internal nodes and the right has n - i. The shared decomposition is the reason all these structures have the same count.

4. The Closed Form — Cₙ = C(2n, n) / (n+1) via the Reflection Principle

The most-celebrated proof of the closed form uses lattice paths and Désiré André’s reflection principle (1887).

4.1 Setup: Dyck Paths

A Dyck path of length 2n is a lattice path from (0, 0) to (2n, 0) using up-steps U = (+1, +1) and down-steps D = (+1, -1) that never goes below the x-axis. Equivalently, it’s a sequence of n Us and n Ds such that every prefix has at least as many Us as Ds.

Claim. The number of Dyck paths of length 2n is Cₙ.

(The bijection with balanced-paren strings: U ↔ (, D ↔ ). A path stays above the axis iff every prefix has more Us than Ds iff the paren string is balanced.)

4.2 The Reflection Argument

Total paths from (0, 0) to (2n, 0) (with no axis restriction) using n Us and n Ds in any order: C(2n, n) (choose which n of 2n steps are U).

We need to subtract the paths that do go below the axis. Such a path touches y = -1 at some point. Let’s count these using the reflection principle.

Bijection. Take any “bad” path (one that touches y = -1). Find the first step where it goes from y = 0 to y = -1. Reflect the entire path up to that point across the line y = -1. The reflected initial segment now starts at (0, -2) and ends at the bad point on y = -1. After the bad point, the path continues unchanged.

So the reflected path starts at (0, -2) and ends at (2n, 0) — a path with (2n + 2) net “ups” minus “downs” balancing to a vertical change of +2. Total steps: 2n. If u is the number of up-steps and d = 2n - u, then u - d = 2, so u = n + 1, d = n - 1.

The number of such paths from (0, -2) to (2n, 0) is C(2n, n + 1) (choose which n + 1 of 2n steps are up).

The bijection is invertible: given a path from (0, -2) to (2n, 0), reflect the part before its first touch of y = -1 to get a “bad” path from (0, 0) to (2n, 0). So bad paths and (0, -2) → (2n, 0) paths are in bijection.

Hence:

Cₙ = (good paths) = (all paths) - (bad paths)
   = C(2n, n) - C(2n, n + 1)

Now compute:

C(2n, n) - C(2n, n + 1)
= (2n)! / (n! · n!) - (2n)! / ((n+1)! · (n-1)!)
= [(2n)! / (n! · (n+1)!)] · [(n+1) - n]              ← common denominator
= (2n)! / (n! · (n+1)!)
= C(2n, n) / (n+1)

So Cₙ = C(2n, n) / (n + 1). ✓ The reflection principle has yielded the closed form via a single bijective argument.

4.3 Generating Function Derivation

Define the generating function C(x) = Σ_{n=0}^{∞} Cₙ · xⁿ. The recurrence C_{n+1} = Σ Cᵢ · C_{n-i} corresponds to the functional equation

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

(the 1 is the n = 0 term; the x · C(x)² is the convolution from the recurrence). Solving the quadratic in C(x):

C(x) = (1 - sqrt(1 - 4x)) / (2x)

(with the − root chosen so C(0) = 1). Expanding the square root in a Taylor series and collecting coefficients gives Cₙ = C(2n, n) / (n + 1) — the same closed form, derived analytically.

The generating function approach generalizes to many enumeration problems; see Wilf’s free book generatingfunctionology or Stanley Enumerative Combinatorics Vol. 2.

5. The Algorithm — Computing Cₙ

5.1 Pseudocode — Direct Closed Form

catalan_closed(n):
    return binomial(2*n, n) / (n + 1)

For exact integer arithmetic (no modulus), this requires arbitrary-precision integer division (the result is always an integer; the division is exact because (n+1) | C(2n, n)).

5.2 Pseudocode — Recurrence

catalan_recurrence(n):
    C := array of length n+1
    C[0] := 1
    for i in 1..n:
        C[i] := 0
        for j in 0..i-1:
            C[i] := C[i] + C[j] * C[i-1-j]
    return C[n]

Time: O(n²). Useful when the recurrence structure matters or for proofs by induction.

5.3 Pseudocode — Modular Arithmetic for Cryptographic / Competitive Use

catalan_mod(n, p):
    # Precompute factorials and inverse factorials mod prime p
    fact, inv_fact := precompute_factorials(2*n, p)
    binomial_2n_n := fact[2n] * inv_fact[n] mod p * inv_fact[n] mod p
    return binomial_2n_n * inverse(n+1, p) mod p          # Fermat: pow(n+1, p-2, p)

O(n) precompute, O(log p) per query.

6. Python Implementation

from math import comb
 
 
def catalan_closed(n: int) -> int:
    """Return C_n via the closed-form formula. Exact integer arithmetic.
 
    Uses Python's arbitrary-precision integers; works for any non-negative n.
    """
    return comb(2 * n, n) // (n + 1)
 
 
def catalan_recurrence(n: int) -> int:
    """Compute Catalan numbers up to C_n via the recurrence. Returns C_n.
 
    Time O(n^2), Space O(n). Slower than closed form but illustrates the recurrence.
    """
    C = [0] * (n + 1)
    C[0] = 1
    for i in range(1, n + 1):
        for j in range(i):
            C[i] += C[j] * C[i - 1 - j]
    return C[n]
 
 
def catalan_iterative(n: int) -> int:
    """Iterative O(n) computation using the multiplicative recurrence.
 
    C_{n+1} = C_n · 2(2n+1) / (n+2). Avoids computing 2n choose n separately.
    """
    c = 1
    for k in range(n):
        c = c * 2 * (2 * k + 1) // (k + 2)
    return c
 
 
def precompute_factorials(N: int, p: int) -> tuple[list[int], list[int]]:
    """Precompute fact[i] = i! mod p, inv_fact[i] = (i!)^(-1) mod p, for i ∈ [0, N]."""
    fact = [1] * (N + 1)
    for i in range(1, N + 1):
        fact[i] = (fact[i - 1] * i) % p
    inv_fact = [1] * (N + 1)
    inv_fact[N] = pow(fact[N], p - 2, p)
    for i in range(N - 1, -1, -1):
        inv_fact[i] = (inv_fact[i + 1] * (i + 1)) % p
    return fact, inv_fact
 
 
def catalan_mod(n: int, p: int, fact: list[int] | None = None, inv_fact: list[int] | None = None) -> int:
    """Compute C_n mod prime p in O(log p) given precomputed factorials, or O(n + log p) without."""
    if fact is None or inv_fact is None:
        fact, inv_fact = precompute_factorials(2 * n, p)
    binom_2n_n = fact[2 * n] * inv_fact[n] % p * inv_fact[n] % p
    return binom_2n_n * pow(n + 1, p - 2, p) % p
 
 
# Demonstrations
if __name__ == "__main__":
    # First 10 Catalan numbers
    expected = [1, 1, 2, 5, 14, 42, 132, 429, 1430, 4862]
    for i, e in enumerate(expected):
        assert catalan_closed(i) == e
        assert catalan_recurrence(i) == e
        assert catalan_iterative(i) == e
 
    # Modular: C_50 mod 10^9+7
    p = 10**9 + 7
    fact, inv_fact = precompute_factorials(200, p)
    assert catalan_mod(50, p, fact, inv_fact) == catalan_closed(50) % p
 
    # Large n: only modular form is feasible
    assert catalan_mod(10000, p) == pow(comb(20000, 10000) // 10001, 1, p)  # consistency check

For competitive programming with mod = 10⁹ + 7, the precompute-and-query pattern is standard. For exact arithmetic, catalan_iterative avoids computing (2n)! directly (which can be enormous) by maintaining the running product.

7. Complexity

7.1 Direct Closed Form

comb(2n, n) is O(n) multiplications of integers up to size n bits. The intermediate is (2n)! (or its conceptual equivalent) — exponentially large in n. For n = 50, Cₙ ≈ 10^28, well beyond 64-bit. Python’s arbitrary-precision integers handle this in microseconds. For modular arithmetic, the intermediate stays bounded by p², so it’s O(1) per multiplication.

7.2 Recurrence

O(n²) arithmetic operations. Each Cᵢ is computed as a sum of i products. Each product is between two bounded-size integers (in modular form) or arbitrary-precision integers (in exact form).

7.3 Iterative Multiplicative

Uses the identity C_{n+1} = C_n · 2(2n+1) / (n+2). This is O(n) multiplications and divisions. The division is exact (the closed form guarantees the result is an integer). Best non-modular form.

7.4 Modular with Precomputation

O(n) to precompute factorials/inverse-factorials up to 2n. Then each C_n mod p query is O(log p) (one Fermat inverse for n + 1). For batched queries the per-query cost amortizes.

8. The 6-8 Most-Important Interpretations (For Interviews)

Out of Stanley’s catalog of 214, these are the interpretations most likely to appear in algorithmic / interview contexts.

8.1 Balanced Parenthesizations of n Pairs

The number of valid strings of n left-parens and n right-parens. Connection: Generate Parentheses (LC 22) generates all Cₙ strings via backtracking. The base case n = 0 is the empty string (C₀ = 1, the empty paren string is “balanced” by convention). Combinatorially: it’s the number of “matchings” of n pairs that don’t cross.

8.2 Distinct Binary Trees with n Nodes

The number of structurally distinct binary trees (or BSTs whose shape is determined by node count) with n internal nodes. Connection: Binary Search Tree (LC 96 “Unique Binary Search Trees” computes this directly). The recurrence: a tree with n + 1 nodes has a root, a left subtree with some i nodes, and a right subtree with n - i nodes. Sum: T_{n+1} = Σ Tᵢ · T_{n-i} — exactly the Catalan recurrence.

8.3 Triangulations of an (n + 2)-Gon

The number of ways to slice a convex polygon with n + 2 vertices into n triangles using non-crossing diagonals. Used in computational geometry (mesh generation), and in Markov chain Monte Carlo over phylogenetic trees.

8.4 Stack-Permutations of n Items

The number of distinct permutations achievable from 1, 2, …, n using a single stack: at any time, you can push the next input number or pop the top of stack to output. The push/pop sequence corresponds to a balanced-paren string, hence Cₙ permutations are achievable.

Concrete: with n = 3, the achievable permutations of 1, 2, 3 are 123, 132, 213, 231, 321 — all 6 except 312. So C₃ = 5 is the count.

This is Knuth’s classic problem (TAOCP Vol. 1 §2.3.4.4), and the unachievable permutations are exactly those containing the pattern 2-3-1 (avoidable patterns of length 3).

8.5 Dyck Paths of Length 2n

Lattice paths from (0, 0) to (2n, 0) using (+1, +1) and (+1, -1) steps, never going below the x-axis. Or equivalently, non-decreasing lattice paths from (0, 0) to (n, n) not crossing the diagonal y = x. Used in queueing theory and probability (the ballot problem).

8.6 Non-Crossing Chord Matchings

Place 2n points on a circle. Match them up into n pairs such that the chords joining matched pairs don’t cross. Number of ways: Cₙ. Used in RNA secondary structure prediction (the matching represents base-pair bonds with the no-crossing constraint reflecting biophysical impossibility of pseudoknots in some models).

8.7 Mountain Ranges with n Upstrokes and n Downstrokes

A “mountain range” of length 2n consisting of n / and n \ strokes, starting and ending at sea level, never going below sea level. Pictorially:

n=3, C_3 = 5 mountain ranges:

   /\         /\          /\     /\           /\/\/\
  /  \      /\/  \       /  \   /  \/\
 /    \    /      \     /    \/\
/_______\  /________\   /__________\   ...

Bijection: / ↔ (, \ ↔ ).

8.8 Number of Ways to Parenthesize n + 1 Factors (Distinct Parsings)

How many ways to fully parenthesize the product x₀ · x₁ · … · xₙ (with n + 1 factors)? Each parenthesization is a distinct way of associating, e.g., ((a · b) · c) · d vs a · ((b · c) · d). The count is Cₙ. The bijection: each parenthesization corresponds to a binary tree with n + 1 leaves (one per factor), and binary trees with n + 1 leaves have count Cₙ. Used in: matrix-chain multiplication problem (the number of distinct multiplication orders is Cₙ, though the optimal order is found via DP — see Matrix Chain Multiplication).

9. Diagram — One Catalan Bijection: Parens ↔ Tree ↔ Path

flowchart LR
  P["((()))"] -->|"each '(' is descend\n each ')' is ascend"| T["Binary Tree:\n  *\n / \\\n*   leaf\n/ \\\n* leaf\n/ \\\nleaf leaf"]
  T -->|"in-order traversal"| Q["Dyck path:\n   /\\/\\/\\\n  /      \\\n /        \\\n/__________\\"]
  Q -->|"  / ↔ (, \\ ↔ )"| P

What this diagram shows. The three Catalan-counted structures — balanced parens, binary trees, Dyck paths — are in bijection. The example traces n = 3 via the string ((())): each ( corresponds to descending into a left child / starting an upstroke; each ) corresponds to returning from a subtree / starting a downstroke. The same 5 = C₃ configurations recur across all three views. The bijection is constructive — given any one representation, the others can be derived mechanically. This is why so many disparate-looking problems all have the answer Cₙ: they reduce, often via these bijections, to a single underlying combinatorial structure (the “Catalan structure”). The diagram emphasizes that knowing one Catalan interpretation gives you, essentially, all the others.

10. Variants and Extensions

10.1 Super-Catalan Numbers (Schröder Numbers)

The large Schröder numbers count lattice paths from (0, 0) to (n, n) using (+1, 0), (0, +1), or (+1, +1) steps, never crossing the diagonal. They generalize Catalan (which forbids the diagonal step). First few: 1, 2, 6, 22, 90, 394, ….

10.2 q-Catalan Numbers

Replace integer factorials with q-factorials (polynomials in q). Used in algebraic combinatorics, especially in connection with the symmetric group and Hecke algebras.

10.3 Narayana Numbers

N(n, k) = (1/n) · C(n, k) · C(n, k-1). They refine Catalan: Σₖ N(n, k) = Cₙ. Each N(n, k) counts the Dyck paths of length 2n with exactly k peaks. Stanley Enumerative Combinatorics Vol. 2 Chapter 6.

10.4 Catalan Triangle / Ballot Numbers

C(n, k) - C(n, k-1) for k ≤ n — counts the number of lattice paths from (0, 0) to (n, k) not touching the diagonal y = x until possibly the end. Used in the ballot problem: in a vote with n + k votes for A and n - k for B, the probability that A always leads is (2k) / (n + k).

10.5 Higher-Dimensional Generalizations

The Fuss-Catalan numbers (1 / (mn + 1)) · C(mn + n, n) count m-ary trees and generalized lattice paths. Recover Catalan with m = 2.

10.6 Connections to Other Sequences

  • Motzkin numbers count similar paths but with a level step allowed: M_n = Σ C(n, 2k) · C_k.
  • Bell numbers count partitions of an n-set; not Catalan, but appear in similar enumeration contexts.
  • Stirling numbers of the second kind count partitions into a fixed number of blocks; orthogonal to Catalan.

11. Pitfalls

11.1 Off-By-One in Indexing

Cₙ is the count for some size-n parameter. The “size” depends on the interpretation: number of pairs (parens), number of internal nodes (trees), n + 2 vertices (polygons). When solving a problem, identify which n is the right index.

11.2 Confusing Cₙ (Catalan) with C(n, k) (Binomial)

The notation collision is ugly. In this note Cₙ is the n-th Catalan; C(n, k) is binomial. Always be explicit in code (catalan(n) vs binomial(n, k)).

11.3 Overflow for Modest n

C₃₀ ≈ 4 · 10^15 — fits in 64 bits. C₃₅ ≈ 4 · 10^18 — borderline. C₄₀ ≈ 1.5 · 10^22 — overflows. Use modular arithmetic or arbitrary-precision integers for n ≥ 35.

11.4 Division in Closed Form

C(2n, n) / (n + 1) is always an integer (provable from the closed form’s combinatorial meaning), but in modular arithmetic, “division” means multiplication by modular inverse. Compute as C(2n, n) · pow(n+1, p-2, p) mod p for prime p. Don’t use Python’s / (which gives a float).

11.5 Recurrence’s Indexing Convention

Some sources write C_{n+1} = Σ Cᵢ · C_{n-i} (this note); others write Cₙ = Σ Cᵢ · C_{n-1-i}. Off-by-one error is rampant. Verify a small case (C₂ = 2 = C₀·C₁ + C₁·C₀ = 1·1 + 1·1) before committing to one form.

11.6 The First Few Values

C₀ = 1, C₁ = 1. Some sources start the sequence at n = 1 with C₁ = 1. The OEIS convention (A000108) starts at n = 0 with C₀ = 1. Check before using.

11.7 Confusing With Mountain Range Pattern Count

A mountain range with n peaks (not n pairs of strokes) is a different count — Motzkin numbers, not Catalan. Specify “n upstrokes and n downstrokes” precisely.

11.8 The “Parenthesization” Interpretation Has Multiple Conventions

“Number of parenthesizations of n + 1 factors” — the answer is Cₙ. “Number of parenthesizations of n factors” — the answer is C_{n-1}. Identify which convention your problem uses.

11.9 BSTs vs Binary Trees

The number of structurally distinct binary trees with n nodes is Cₙ. The number of labeled binary search trees with n nodes whose in-order traversal is a fixed sequence (e.g., 1, 2, …, n) is also Cₙ (the labels are forced by the BST property). Some textbooks confuse these; both happen to equal Cₙ.

11.10 Asymptotic Approximation

Cₙ ~ 4ⁿ / (n^(3/2) √π). For n = 100, the approximation gives ~9 · 10^57, very close to the exact ≈ 8.96 · 10^57. For small n (≤ 10), the approximation is too rough; use the closed form.

12. Common Interview Problems

ProblemLeetCode # / SourceConnection
Generate ParenthesesLC 22Generate all Cₙ balanced strings via backtracking
Valid ParenthesesLC 20Check balance — easy compared to enumeration
Unique Binary Search TreesLC 96Count: Cₙ (closed form or DP)
Unique Binary Search Trees IILC 95Generate all Cₙ distinct BST structures
Different Ways to Add ParenthesesLC 241Enumerate parenthesizations of expression
Number of Ways to Reorder BSTLC 1569Variant; uses Catalan + binomial
Triangle Pattern CountingLC …Triangulations of polygon → Catalan
Dyck Path VariantscompetitiveVariants on the basic Dyck count
Catalan number of order n mod pcompetitive standardClosed form with modular inverse
Number of stack-sortable permutationscompetitiveCatalan; equivalent to “no 2-3-1 pattern”
Mountain Array CountingLC 941, 1671Variants; sometimes Catalan, sometimes simpler
Matrix Chain Multiplication (count, not optimize)competitiveNumber of ways to fully parenthesize n matrices = C_{n-1}
Non-crossing perfect matchings of 2n pointscompetitiveDirect Catalan
Number of Mountain RangescompetitiveDirect Catalan

13. Open Questions

  • Do all 214 of Stanley’s interpretations have efficient bijections to each other? Most do; some are deep theorems requiring nontrivial bijection arguments. The systematic study is at the heart of bijective combinatorics.
  • Are there efficient algorithms to enumerate (not just count) all Cₙ Catalan structures of size n? Yes — for parens / trees / Dyck paths, O(Cₙ) total time enumeration via standard backtracking, optimal up to constants. For more exotic interpretations, custom enumeration algorithms are needed.
  • Is Cₙ ever prime? C₂ = 2 (prime). C₃ = 5 (prime). All Cₙ for n ≥ 4 are composite — provable from the closed form Cₙ = C(2n, n) / (n+1) via factorization arguments.
  • What is the asymptotic distribution of properties of random Catalan structures? Heavy active research in probabilistic combinatorics; for example, the height of a random Dyck path of length 2n is Θ(√n) with a specific limiting distribution.

14. See Also

Graph View

Backlinks