# Catalan Numbers

A sequence counting many structurally similar objects — balanced parentheses, binary trees, non-crossing partitions — all in bijection with each other.

**Rests on:** Proof by Induction

*Mathematical Foundations · Discrete Mathematics*


## Why learn this

You often face problems where a large task is made up of smaller, similar tasks, and you need to know how many different ways those pieces can be arranged. The Catalan numbers give you the exact count for several common situations: arranging matching parentheses, building tournament brackets, or triangulating a polygon. Knowing these numbers helps you predict the complexity of structures that grow in a specific, balanced way, which is useful when designing systems that rely on nested layers, such as file directories or logical expressions.


## The intuition

Imagine you have pairs of matching parentheses and you want to arrange them so they are correctly nested. This means every opening parenthesis '(' must have a corresponding closing parenthesis ')' that comes later, and at no point while reading from left to right do you encounter more closing parentheses than opening ones.

Let us count the ways for small numbers of pairs:
- With 1 pair: There is only 1 way: ()
- With 2 pairs: There are 2 ways: ()() and (())
- With 3 pairs: There are 5 ways: ((())), (()()), (())(), ()(()), and ()()

The sequence of counts is 1, 1, 2, 5, 14, 42, and so on. These numbers appear whenever you split a structure into two smaller, independent parts of the same type. For instance, in the case of parentheses, the first opening parenthesis must match some closing parenthesis. Everything inside that pair forms one valid sequence, and everything outside it forms another valid sequence. The total count for n pairs is the sum of the products of the counts for all possible ways to split the remaining items between the inside and the outside.


## An analogy

Think of a knockout sports tournament with 8 teams. The final match determines the winner. This final match splits the tournament into two independent halves: the left bracket, containing some number of teams, and the right bracket, containing the rest. If you want to know how many different ways you can structure the brackets for 8 teams (ignoring which specific team is in which bracket), you look at every possible split of the teams between the two semi-finals. If one semi-final has 6 teams and the other has 2, you multiply the number of bracket structures for 6 by the number for 2. You do this for every valid split (1 vs 7, 2 vs 6, 3 vs 5, 4 vs 4) and add the results up. This process relies on a full binary tree, which is a structure where every node has either zero or exactly two children, representing the matches. The analogy works for counting structures but fails if you care about team identities or seedings, as Catalan numbers only count the shape of the bracket, not who plays whom.


## Definition

The Catalan numbers are a sequence of integers that count the number of ways to correctly nest n pairs of items, such as parentheses, or to structure a binary tree with n+1 leaves, using the rule that the whole is built by combining smaller valid structures in every possible way.


## How it connects

This concept sits within combinatorics, the study of counting. It connects directly to recursion, because each Catalan number is calculated by summing products of earlier numbers, and to binary trees, which are hierarchical data structures where each node has at most two children.


## The mathematics

The Catalan numbers are a sequence of integers that grow quickly. The first few are 1, 1, 2, 5, 14, 42, 132, and so on. They are defined by a recurrence relation: the nth Catalan number, often written C_n, is the sum over all k from 0 to n-1 of C_k times C_{n-1-k}. In plain words: to arrange n pairs of parentheses, pick a split point — the first opening bracket will eventually match with some closing bracket, and inside that pair there will be some number of pairs, say k, and outside there will be n-1-k pairs. For each such split, the number of valid arrangements is the number of ways to arrange the inside times the number of ways to arrange the outside. Summing over all splits gives the total. The base case is C_0 = 1 — there is exactly one way to arrange zero pairs: nothing. This recurrence is a perfect example of a recursive decomposition: breaking a problem of size n into two smaller independent subproblems, one of size k and one of size n-1-k, and combining the counts by multiplication.

The nth Catalan number is given by the recurrence: C_n = \sum_{k=0}^{n-1} C_k \cdot C_{n-1-k}, with base case C_0 = 1. A closed-form expression is C_n = \frac{1}{n+1} \binom{2n}{n}, where \binom{2n}{n} is the binomial coefficient — the number of ways to choose n items from 2n.


## A worked example

```
Let's compute the first four Catalan numbers by hand, starting from the base case C_0 = 1. We'll use the recurrence: C_n = sum_{k=0}^{n-1} C_k * C_{n-1-k}.

Step 1: C_0 = 1 (base case)   # There is exactly one way to arrange zero pairs of parentheses: do nothing.
Step 2: C_1 = C_0 * C_0 = 1 * 1 = 1   # For one pair, k can only be 0 (inside is empty, outside has 0 pairs). So C_1 = C_0 * C_0 = 1.
Step 3: C_2 = C_0*C_1 + C_1*C_0 = 1*1 + 1*1 = 2   # For two pairs, k can be 0 or 1. If k=0, inside is empty and outside has 1 pair; if k=1, inside has 1 pair and outside is empty. Each product is 1, summed gives 2.
Step 4: C_3 = C_0*C_2 + C_1*C_1 + C_2*C_0 = 1*2 + 1*1 + 2*1 = 5   # Splits: k=0 (inside empty, outside 2 pairs), k=1 (inside 1, outside 1), k=2 (inside 2, outside empty). Summing products: 2 + 1 + 2 = 5.
Step 5: C_4 = C_0*C_3 + C_1*C_2 + C_2*C_1 + C_3*C_0 = 1*5 + 1*2 + 2*1 + 5*1 = 14   # Following the same pattern, summing over k=0 to 3 gives 5 + 2 + 2 + 5 = 14.

Result: The first five Catalan numbers are C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5, and C_4 = 14. The sequence continues 42, 132, 429, and so on.
```


## From scratch, in Python

```python
def catalan(n):
    # base case
    if n == 0:
        return 1
    # use a list to store computed values
    C = [0] * (n + 1)
    C[0] = 1
    for i in range(1, n + 1):
        total = 0
        for k in range(i):
            total += C[k] * C[i - 1 - k]
        C[i] = total
    return C[n]

# Test
for n in range(6):
    print(f"C_{n} = {catalan(n)}")
```


## What the code does

The function `catalan(n)` computes the nth Catalan number using the recurrence we derived. First, we handle the base case: if n is 0, we return 1. Then we create a list `C` of length n+1, initially all zeros, and set `C[0] = 1`. The list `C` stores previously computed Catalan numbers so we don't recompute them — this is the same idea as memoisation or dynamic programming. The outer loop runs from 1 to n, computing each in turn. For each i, we set a running total to 0, then loop over all possible splits k. For each k, we multiply the number of ways for the inside (C[k]) by the number of ways for the outside (C[i-1-k]) and add to total. After the inner loop, we store total at C[i]. Finally, we return C[n]. The loops illustrate the recurrence in code: nested loops correspond to the double sum, and the list is a table of values we fill up step by step. This code is pure Python, using only lists and loops — no external libraries needed.


## Common misconceptions

**Catalan numbers count only parentheses** — Catalan numbers are just about brackets.

Parentheses are one of many objects they count; they also count binary trees, non-crossing partitions, polygon triangulations, and more. In fact: Catalan numbers count any structure that splits recursively into two independent parts — parentheses are just the most intuitive example.

**The recurrence is the formula** — The recurrence is the only definition.

There is also a closed form using binomial coefficients, which gives a direct formula without recursion. In fact: The recurrence is one way to define them; a closed-form expression exists, but the recurrence reveals the recursive structure.

**The nth Catalan number is about n items** — C_n counts arrangements of n objects.

Specifically, C_n counts arrangements of n pairs, so there are 2n items in total (e.g., n opening and n closing brackets). In fact: C_n involves 2n symbols in total when thinking of parentheses, but the size parameter is the number of pairs.

**The sequence starts with 1, 2, 5** — The Catalan numbers are 1, 2, 5, 14...

This misses C_0 = 1 and C_1 = 1. In fact: The full sequence is 1, 1, 2, 5, 14, 42, 132, ... starting with C_0 = 1.


## In short

Catalan numbers count objects that split into two independent parts. They satisfy a recurrence that mirrors splitting a problem in two, and they appear across combinatorics — balanced parentheses, binary trees, and more. Recognising the Catalan pattern often reveals a recursive decomposition, leading to efficient algorithms.


## Where this is used

Catalan numbers appear across computer science, and by extension in AI systems, whenever a problem involves recursive decomposition into two independent subproblems. In large language models (LLMs), the parsing of natural language and code relies on grammar-based parsing, where the syntax of a sentence or program is represented as a parse tree. The number of ways to parse a sentence under a context-free grammar — when there is ambiguity — can be exponential, and Catalan numbers are the canonical example of the number of binary tree structures. For instance, the number of ways to associate a sequence of operations, like a string of additions, is a Catalan number. In practice, LLMs use attention mechanisms, which are computed over sequences; while attention itself does not use Catalan numbers directly, the training data includes code and mathematical expressions where the underlying structures are counted by Catalan numbers. In small language models running on phones or laptops, the constraints of memory and computation force efficiency in parsing and generation. Dynamic programming algorithms for parsing, such as the CYK algorithm, rely on the same splitting structure as the Catalan recurrence, storing intermediate results for substrings. Retrieval-augmented generation (RAG) involves embedding documents and querying for relevant chunks. While the embedding itself is a vector, the indexing structures — such as hierarchical navigable small world graphs — are not Catalan directly, but the concept of recursively partitioning data into two halves is reminiscent. Agentic systems that plan and call tools often use tree search algorithms, like Monte Carlo tree search, which build a tree of states and actions. The branching structure of a complete binary tree, and the number of full binary trees with n internal nodes, is a Catalan number. While the search tree is not necessarily Catalan in its growth (it is pruned and expands) , the theoretical count of possible plans under certain constraints can involve Catalan numbers. In everyday applied machine learning, decision trees and random forests build hierarchical partitions of data. A decision tree chooses a split at each node, partitioning the data into two subsets, and each subset is recursively split. The number of possible full binary decision trees with a given number of leaves is counted by Catalan numbers, which gives a sense of the hypothesis space. In practice, however, learning algorithms use greedy heuristics rather than enumerating all trees. A developer writing code for tree-based models in scikit-learn does not explicitly invoke Catalan numbers, but the underlying structural understanding informs algorithm design, such as limiting tree depth to avoid overfitting. Building software with this concept rarely requires direct computation of Catalan numbers. More often, a developer will write a recursive function that splits a problem in two, like building a parse tree or a decision tree, and the Catalan numbers provide a theoretical count of how many such structures exist. What can break if this is done badly is an explosion in complexity: if the recursion does not memoise overlapping subproblems, it becomes exponential, as the naive Fibonacci-like implementation of the recurrence would be. Understanding the recurrence helps you recognise when to use dynamic programming.


---

Read this on the web: https://basavapurushottam.com/learn-ai/catalan-numbers
