Catalan Numbers

Count the ways to arrange two pairs of balanced parentheses: (()) and ()() — that's 2. With three pairs the answer is 5: ((())), (()()), (())(), ()(()), ()()(). With four pairs: 14.

The sequence 1, 1, 2, 5, 14, 42, 132, 429… is called the Catalan numbers, named after the Belgian mathematician Eugène Charles Catalan, who studied them in the 1830s. (The sequence was actually known earlier to Chinese mathematician Mingantu around 1730, and to Leonhard Euler.)

What makes the Catalan numbers remarkable is not just their growth — they grow roughly as $\frac{4^n}{n\sqrt{n}}$ — but their uncanny habit of showing up in completely different counting problems that all turn out to share the same answer:

• Balanced bracket strings of length 2n
• Full binary trees with n+1 leaves
• Triangulations of a convex polygon with n+2 vertices
• Paths below the diagonal in an n×n grid
• Ways to multiply a chain of n+1 numbers (parenthesizing a product)
• And more than 200 other combinatorial families

Each of these is a different problem with the same count. That can't be a coincidence — and it isn't. Every one of them satisfies the same recurrence, and that shared structure is the key to understanding why the sequence is so universal.

Choose a value of n (the number of pairs of brackets). The demo lists every balanced string of length 2n and counts them. Watch the count match the Catalan number $C_{n}$ exactly.

<p class="hint">Pick <b>n</b> to see every balanced bracket string of length 2n listed below.
    The count at the top always matches the Catalan number <b>C<sub>n</sub></b>.</p>
<div class="controls">
  <label>n =
    <input id="nInput" type="range" min="0" max="6" value="3" />
    <span id="nVal">3</span>
  </label>
</div>
<div class="stats" id="stats"></div>
<ul id="list" class="str-list"></ul>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .6rem; margin-bottom: .7rem; font-size: .95rem; }
label { display: flex; align-items: center; gap: .5rem; font-weight: 600; }
input[type=range] { accent-color: #1d3557; width: 180px; }
.stats { font-size: 1rem; font-weight: 700; margin-bottom: .6rem; color: #1d3557; min-height: 1.4em; }
.str-list { list-style: none; margin: 0; padding: 0; display: flex; flex-wrap: wrap; gap: 6px; max-height: 300px; overflow-y: auto; }
.str-list li { font-family: ui-monospace, monospace; font-size: .92rem; background: #e8eef3; color: #1d3557; border: 1px solid #c3d0dc; border-radius: 6px; padding: .2rem .5rem; white-space: nowrap; }
.str-list li.highlight { background: #1d3557; color: #fff; border-color: #1d3557; }
.cap-note { font-size: .82rem; color: #666; margin-top: .5rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Catalan number demo: generate all balanced bracket strings of length 2n.
// C(n) = (1/(n+1)) * C(2n, n) — the count always matches the Catalan number.
// Algorithm: recursive generation ensuring at no prefix do closing brackets
// exceed opening brackets.

const MAX_LIST = 6; // max n for listing (C(7)=429 would be too slow to render)

function catalan(n) {
  // Use the recurrence: C(0)=1, C(n) = sum_{i=0}^{n-1} C(i)*C(n-1-i)
  const C = new Array(n + 1).fill(0n);
  C[0] = 1n;
  for (let k = 1; k <= n; k++) {
    for (let i = 0; i < k; i++) C[k] += C[i] * C[k - 1 - i];
  }
  return C[n];
}

// Generate all balanced strings of n pairs using backtracking.
function generate(n) {
  const results = [];
  function bt(s, open, close) {
    if (s.length === 2 * n) { results.push(s); return; }
    if (open < n)  bt(s + '(', open + 1, close);
    if (close < open) bt(s + ')', open, close + 1);
  }
  bt('', 0, 0);
  return results;
}

const nInput = document.getElementById('nInput');
const nVal   = document.getElementById('nVal');
const stats  = document.getElementById('stats');
const list   = document.getElementById('list');

function render() {
  const n = parseInt(nInput.value, 10);
  nVal.textContent = n;
  const cn = catalan(n);
  stats.textContent = `C${n} = ${cn}  ← ${n === 0 ? 'empty string' : fmt('balanced strings of length %v%', { v: 2 * n })}`;

  list.innerHTML = '';
  if (n === 0) {
    const li = document.createElement('li');
    li.className = 'highlight';
    li.textContent = '(empty)';
    list.appendChild(li);
    return;
  }
  if (n > MAX_LIST) {
    const note = document.createElement('p');
    note.className = 'cap-note';
    note.textContent = fmt('Listing %cn% strings would be slow — showing count only for n > %MAX_LIST%.', { cn: cn, MAX_LIST: MAX_LIST });
    list.appendChild(note);
    return;
  }
  const strings = generate(n);
  strings.forEach((s, idx) => {
    const li = document.createElement('li');
    if (idx === 0) li.className = 'highlight';
    li.textContent = s;
    list.appendChild(li);
  });

  // Verify: count must equal Catalan number
  console.assert(
    BigInt(strings.length) === cn,
    `BUG: generated ${strings.length} strings but C(${n}) = ${cn}`
  );
  console.log(fmt('n=%n%: generated %length% strings, C(%n%)=%cn% ✓', { n: n, length: strings.length, cn: cn }));
}

nInput.addEventListener('input', render);
render();

<p class="hint">Pick <b>n</b> to see every balanced bracket string of length 2n listed below.
    The count at the top always matches the Catalan number <b>C<sub>n</sub></b>.</p>
<div class="controls">
  <label>n =
    <input id="nInput" type="range" min="0" max="6" value="3" />
    <span id="nVal">3</span>
  </label>
</div>
<div class="stats" id="stats"></div>
<ul id="list" class="str-list"></ul>

* { box-sizing: border-box; }
body { font-family: system-ui, sans-serif; color: #222; margin: 0; }
.hint { font-size: .9rem; color: #444; margin: 0 0 .8rem; line-height: 1.45; }
.controls { display: flex; align-items: center; gap: .6rem; margin-bottom: .7rem; font-size: .95rem; }
label { display: flex; align-items: center; gap: .5rem; font-weight: 600; }
input[type=range] { accent-color: #1d3557; width: 180px; }
.stats { font-size: 1rem; font-weight: 700; margin-bottom: .6rem; color: #1d3557; min-height: 1.4em; }
.str-list { list-style: none; margin: 0; padding: 0; display: flex; flex-wrap: wrap; gap: 6px; max-height: 300px; overflow-y: auto; }
.str-list li { font-family: ui-monospace, monospace; font-size: .92rem; background: #e8eef3; color: #1d3557; border: 1px solid #c3d0dc; border-radius: 6px; padding: .2rem .5rem; white-space: nowrap; }
.str-list li.highlight { background: #1d3557; color: #fff; border-color: #1d3557; }
.cap-note { font-size: .82rem; color: #666; margin-top: .5rem; }

const fmt = (s, v) => s.replace(/%(\w+)%/g, (_, k) => String(v[k] ?? ''));
// Catalan number demo: generate all balanced bracket strings of length 2n.
// C(n) = (1/(n+1)) * C(2n, n) — the count always matches the Catalan number.
// Algorithm: recursive generation ensuring at no prefix do closing brackets
// exceed opening brackets.

const MAX_LIST = 6; // max n for listing (C(7)=429 would be too slow to render)

function catalan(n) {
  // Use the recurrence: C(0)=1, C(n) = sum_{i=0}^{n-1} C(i)*C(n-1-i)
  const C = new Array(n + 1).fill(0n);
  C[0] = 1n;
  for (let k = 1; k <= n; k++) {
    for (let i = 0; i < k; i++) C[k] += C[i] * C[k - 1 - i];
  }
  return C[n];
}

// Generate all balanced strings of n pairs using backtracking.
function generate(n) {
  const results = [];
  function bt(s, open, close) {
    if (s.length === 2 * n) { results.push(s); return; }
    if (open < n)  bt(s + '(', open + 1, close);
    if (close < open) bt(s + ')', open, close + 1);
  }
  bt('', 0, 0);
  return results;
}

const nInput = document.getElementById('nInput');
const nVal   = document.getElementById('nVal');
const stats  = document.getElementById('stats');
const list   = document.getElementById('list');

function render() {
  const n = parseInt(nInput.value, 10);
  nVal.textContent = n;
  const cn = catalan(n);
  stats.textContent = `C${n} = ${cn}  ← ${n === 0 ? 'empty string' : fmt('balanced strings of length %v%', { v: 2 * n })}`;

  list.innerHTML = '';
  if (n === 0) {
    const li = document.createElement('li');
    li.className = 'highlight';
    li.textContent = '(empty)';
    list.appendChild(li);
    return;
  }
  if (n > MAX_LIST) {
    const note = document.createElement('p');
    note.className = 'cap-note';
    note.textContent = fmt('Listing %cn% strings would be slow — showing count only for n > %MAX_LIST%.', { cn: cn, MAX_LIST: MAX_LIST });
    list.appendChild(note);
    return;
  }
  const strings = generate(n);
  strings.forEach((s, idx) => {
    const li = document.createElement('li');
    if (idx === 0) li.className = 'highlight';
    li.textContent = s;
    list.appendChild(li);
  });

  // Verify: count must equal Catalan number
  console.assert(
    BigInt(strings.length) === cn,
    `BUG: generated ${strings.length} strings but C(${n}) = ${cn}`
  );
  console.log(fmt('n=%n%: generated %length% strings, C(%n%)=%cn% ✓', { n: n, length: strings.length, cn: cn }));
}

nInput.addEventListener('input', render);
render();

Notice: for n = 4 the list already has 14 strings and for n = 5 it jumps to 42. The count grows quickly — roughly four times larger each step. Yet computing the count (via the formula or recurrence) takes only a moment; listing all strings gets expensive fast, which is why large n values are intentionally capped in the demo.

Catalan numbers are a solved counting problem — their status is "closed-form formula, proven exact":

The formula (due to Euler and Catalan, proven rigorously in the 19th century):

$$C_n = \frac{1}{n+1}\binom{2n}{n}$$

where $\binom{2n}{n} = \frac{(2n)!}{n!\, n!}$ is the central binomial coefficient.

• Computing $C_{n}$ takes $O(n)$ arithmetic operations — trivially fast for any reasonable n.
• The recurrence: $C_0 = 1$, and $C_n = \sum_{i=0}^{n-1} C_i \cdot C_{n-1-i}$. This splits a structure of size n at every possible "first cut" and multiplies the choices on each side — the same pattern appears in parenthesizations, tree builds, and triangulations.
• Listing all Catalan structures of order n takes $O(C_{n})$ time — unavoidably exponential, since there are $C_{n}$ of them and each must be output. This is the domain of #P counting complexity.
• Asymptotically: $C_n \approx \frac{4^n}{n^{3/2}\sqrt{\pi}}$, so the count grows like $4^n$ — exponential in n.

The key insight is the universality of the recurrence. Whenever a combinatorial family splits cleanly at a "pivot" that divides the structure into two independent sub-structures, and the sub-structure counts multiply, the Catalan numbers appear. This is why so many unrelated problems share the same answer.

Because the Catalan numbers count so many fundamental combinatorial structures, they appear wherever computers or mathematicians need to reason about those structures:

• Compiler design: expression parsing and abstract syntax trees are counted by Catalan numbers — the number of different parse trees for an ambiguous grammar is a Catalan-related count.
• Database query optimization: the number of ways to join n tables (each join order is a binary tree over n leaves) is exactly $C_{n-1}$. With 10 tables that's 4,862 possible join orders, and choosing the best is why query optimizers are complex.
• RNA secondary structure: the number of non-crossing base-pair matchings of an RNA strand is a Catalan number — this is a foundational model in computational biology.
• Random generation: Catalan structures (random binary trees, random triangulations) are used in average-case analysis and probabilistic algorithms.
• Type theory and logic: proof trees in sequent calculus, legal bracketings in type expressions, and monad associativity laws all have Catalan-number cardinalities.

The common thread: whenever a problem involves non-crossing matchings, recursive decomposition at a split point, or well-nested structures, look for Catalan numbers.

The Catalan numbers are one of combinatorics' great gifts: a single sequence — 1, 1, 2, 5, 14, 42… — computed in an instant by the formula $C_n = \frac{1}{n+1}\binom{2n}{n}$, yet hiding inside balanced brackets, binary tree shapes, polygon triangulations, and more than 200 other combinatorial families.

Their universality is not magic. It traces back to the same recurrence: split the structure at a pivot, count the left part, count the right part, multiply, sum over all pivots. Any family that decomposes this way will share the Catalan count.

So whenever you see a recursive structure with a clean binary split, ask: is this secretly Catalan? The answer is yes more often than you'd expect — and the proof is usually just a bijection away.