Counting the number of valid bracket (parenthesis) sequences formed by $n$ opening brackets ( and $n$ closing brackets ) is one of the most celebrated problems in combinatorics and computer science.
Whether you are parsing expressions, counting binary trees, or analyzing stack permutations, the answer is always the $n$-th Catalan number:
\[ C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}. \]In this post, we will formally define valid bracket sequences, build geometric intuition using lattice paths (Dyck paths), and prove the closed-form formula using André’s Reflection Principle as well as the first-return recurrence relation.
1. What Makes a Bracket Sequence Valid?
A sequence of length $2n$ consisting of $n$ opening brackets ( and $n$ closing brackets ) is valid (or well-formed) if and only if:
- Total Balance: There are exactly $n$ opening brackets
(and $n$ closing brackets). - Prefix Balance: In every prefix of the sequence, the number of closing brackets
)never exceeds the number of opening brackets(.
For small values of $n$, we can list all valid sequences directly:
| $n$ | Valid Bracket Sequences | Count ($C_n$) |
|---|---|---|
| $0$ | $\epsilon$ (empty string) | $1$ |
| $1$ | () | $1$ |
| $2$ | (()), ()() | $2$ |
| $3$ | ((())), (()()), (())(), ()(()), ()()() | $5$ |
| $4$ | $14$ distinct sequences | $14$ |
Without condition 2, there are simply $\binom{2n}{n}$ ways to choose which $n$ of the $2n$ positions hold (. Our goal is to determine how many of those $\binom{2n}{n}$ sequences satisfy the prefix condition everywhere.
2. Geometric Intuition: Lattice Paths and Dyck Paths
We can translate any sequence of $n$ opening brackets ( and $n$ closing brackets ) into a monotonic path on an $n \times n$ grid starting at $(0, 0)$ and ending at $(n, n)$:
- Each opening bracket
(moves 1 step right (East): $(x, y) \to (x + 1, y)$. - Each closing bracket
)moves 1 step up (North): $(x, y) \to (x, y + 1)$.
At any point $(x, y)$ along the path:
- $x$ is the number of
(seen so far. - $y$ is the number of
)seen so far.
Therefore, the Prefix Balance condition ($y \le x$ at all times) has a clean geometric meaning:
A bracket sequence is valid if and only if its lattice path from $(0,0)$ to $(n,n)$ never crosses above the main diagonal $y = x$.
Such a path is called a Dyck path of order $n$.
Figure 1: Mapping bracket sequences of $n=3$ pairs onto a $3\times 3$ lattice grid. Any invalid sequence must touch the forbidden line $y = x + 1$.
3. Proof 1: André’s Reflection Principle
Instead of counting valid paths directly, it is much easier to count the invalid (“bad”) paths and subtract them from the total $\binom{2n}{n}$ paths:
\[ C_n = \text{Total Paths} - \text{Bad Paths} = \binom{2n}{n} - \text{Bad Paths}. \]Characterizing Bad Paths
Since steps have size $1$, a path from $(0, 0)$ to $(n, n)$ crosses above the diagonal $y = x$ if and only if it touches or crosses the forbidden line:
\[ y = x + 1. \]Let $P$ be any bad path from $(0, 0)$ to $(n, n)$, and let $M = (k, k + 1)$ be the first point where $P$ touches the line $y = x + 1$.
Now, perform a geometric reflection on the portion of $P$ that occurs after point $M$ across the line $y = x + 1$:
- Every remaining East step (
() after $M$ becomes a North step ()). - Every remaining North step (
)) after $M$ becomes an East step (().
Figure 2: André’s Reflection Principle. Reflecting the suffix of any bad path after its first contact $M$ with $y = x + 1$ creates a one-to-one bijection with all paths from $(0,0)$ to $(n-1, n+1)$.
Where Does the Reflected Path End?
Let’s track the coordinates before and after $M = (k, k + 1)$:
- From $(0, 0)$ to $M$, the path took $k$ East steps and $k + 1$ North steps.
- In the original path to $(n, n)$, the remaining suffix after $M$ had to take:
- $n - k$ East steps, and
- $n - (k + 1)$ North steps.
- After reflecting the suffix across $y = x + 1$, the East and North steps in the suffix are swapped! So the reflected suffix takes:
- $n - k - 1$ East steps, and
- $n - k$ North steps.
Adding the steps before $M$ and the reflected steps after $M$, the reflected path always terminates at:
\[ \big(k + (n - k - 1),\; (k + 1) + (n - k)\big) = (n - 1,\, n + 1). \]Why Is This a Bijection?
- Every bad path from $(0, 0)$ to $(n, n)$ touches $y = x + 1$ at a unique first point $M$, so reflecting after $M$ maps it to a unique path from $(0, 0)$ to $(n - 1, n + 1)$.
- Conversely, every monotonic path from $(0, 0)$ to $(n - 1, n + 1)$ starts below $y = x + 1$ (since $0 < 1$) and ends above $y = x + 1$ (since $n + 1 > (n - 1) + 1$). Therefore, it must cross the line $y = x + 1$ at some first point $M$; reflecting the suffix after $M$ recovers the unique bad path to $(n, n)$.
Because this mapping is a bijection, the number of bad paths from $(0, 0)$ to $(n, n)$ equals the total number of monotonic paths from $(0, 0)$ to $(n - 1, n + 1)$:
\[ \text{Bad Paths} = \binom{(n - 1) + (n + 1)}{n + 1} = \binom{2n}{n + 1}. \]Subtracting Bad Paths from Total Paths
Subtracting the bad paths from all $\binom{2n}{n}$ paths yields the $n$-th Catalan number:
\[ \begin{aligned} C_n &= \binom{2n}{n} - \binom{2n}{n+1} \\[6pt] &= \binom{2n}{n} - \frac{n}{n+1}\binom{2n}{n} \\[6pt] &= \frac{1}{n+1}\binom{2n}{n}. \quad \blacksquare \end{aligned} \]4. Proof 2: First-Return Decomposition & Recurrence
We can also prove that valid bracket sequences follow the Catalan recurrence without using geometry.
Take any non-empty valid bracket sequence $S$ of $n \ge 1$ pairs. Its very first character must be an opening bracket (. Because $S$ is balanced, that first ( has a unique matching closing bracket ) where the prefix balance returns to $0$ for the first time.
This uniquely decomposes $S$ into two independent valid bracket sub-sequences $A$ and $B$:
\[ S = \texttt{(} \, A \, \texttt{)} \, B \]
Figure 3: Every non-empty valid bracket sequence decomposes uniquely as $S = \texttt{(} A \texttt{)} B$, where $A$ has $k$ pairs and $B$ has $n - 1 - k$ pairs.
- Inside the first matched pair, $A$ can contain $k$ pairs of brackets (where $0 \le k \le n - 1$) and must itself be a valid bracket sequence ($C_k$ ways).
- Outside, $B$ contains the remaining $n - 1 - k$ pairs of brackets and must also be a valid bracket sequence ($C_{n - 1 - k}$ ways).
Summing over all possible sizes $k \in \{0, 1, \dots, n - 1\}$ gives the Catalan recurrence relation:
\[ C_0 = 1, \qquad C_n = \sum_{k=0}^{n-1} C_k \, C_{n-1-k} \quad (n \ge 1). \]Using ordinary generating functions $G(x) = \sum_{n=0}^{\infty} C_n x^n$, the convolution above translates to:
\[ G(x) = 1 + x \, G(x)^2 \implies G(x) = \frac{1 - \sqrt{1 - 4x}}{2x}, \]whose Taylor expansion via the generalized binomial theorem yields the exact same formula $C_n = \frac{1}{n+1}\binom{2n}{n}$.
5. Summary
| Perspective | Key Idea | Formula |
|---|---|---|
| Subtraction / Reflection | Total paths to $(n,n)$ minus paths touching $y = x + 1$ | $\displaystyle\binom{2n}{n} - \binom{2n}{n+1}$ |
| Closed Form | Algebraic simplification of the reflection formula | $\displaystyle\frac{1}{n+1}\binom{2n}{n}$ |
| Recursive Decomposition | Partition at first return to zero: $S = \texttt{(} A \texttt{)} B$ | $\displaystyle\sum_{k=0}^{n-1} C_k C_{n-1-k}$ |