Catalan Numbers

A market maker's inventory over a trading day goes up on buys and down on sells, and by close it must return to flat — but it can never go net short of the position limit in between. How many distinct valid sequences of ups and downs achieve this? Naive counting overcounts wildly, because most random sequences dip below the limit at some point and have to be thrown out. There's a single, elegant integer sequence that counts exactly this kind of "balanced, never-goes-negative" path — the Catalan numbers — and it counts several unrelated-looking problems too.

An analogy: matched parentheses

Think of a string of open and close parentheses, like (()()). It's "valid" if, reading left to right, you never have more closes than opens so far, and you end with them equal. (() is invalid — it never closes. The number of valid arrangements of $n$ pairs is the $n$-th Catalan number. A market maker's flat-to-flat, never-below-limit inventory path is the same structure: "open" is a buy, "close" is a sell, and staying non-negative is staying above the limit.

The formula, one piece at a time

Let $C_n$ denote the $n$-th Catalan number, counting balanced sequences made of $n$ "up" moves and $n$ "down" moves that never go negative. It has a closed form:

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \frac{(2n)!}{(n+1)!\,n!} .$$

In words: take the number of ways to arrange $n$ ups and $n$ downs in any order — that's $\binom{2n}{n}$, "$2n$ choose $n$" — and divide by $n+1$. That division is the correction removing every arrangement that dips negative; it falls out of a clever mapping (the reflection principle) that pairs each "bad" path with a unique reflected path in the full, unconstrained count. $C_n$ also satisfies a recurrence built from splitting a path at its first return to zero:

$$C_{n+1} = \sum_{i=0}^{n} C_i \, C_{n-i}, \qquad C_0 = 1 .$$

In words: a balanced sequence of length $n+1$ either returns to zero for the first time after some prefix of length $i$, followed by a balanced sequence of the remaining $n-i$ — summing over every possible first-return point $i$ builds every valid sequence exactly once.

Worked example 1: counting order sequences by hand

For $n = 3$ (3 buys, 3 sells, inventory never negative): $C_3 = \frac{1}{4}\binom{6}{3} = \frac{1}{4} \times 20 = 5$. Listing them confirms it: with B for buy (+1) and S for sell (−1), the 5 valid sequences are BBBSSS, BBSBSS, BBSSBS, BSBBSS, BSBSBS. Every other arrangement of three B's and three S's (there are $\binom{6}{3}=20$ total) dips the running total below zero at some point and is excluded.

Worked example 2: binary tree shapes

Catalan numbers also count the number of distinct shapes of a binary tree with $n$ internal nodes — relevant when counting ways to fully parenthesize a chain of $n+1$ matrix multiplications (each parenthesization is one tree shape, and picking the cheapest is the matrix-chain optimization problem). For $n = 4$: $C_4 = \frac{1}{5}\binom{8}{4} = 14$ — 14 distinct ways to parenthesize a product of 5 matrices, each a different tree shape and, in general, a different total cost.

What this means in practice

Catalan numbers appear anywhere something must stay "balanced" or non-negative while returning to its starting state: matched brackets in a parser, ways to triangulate a polygon, and counting inventory paths that respect a risk limit. Recognizing a "balanced path, never negative, ends at zero" structure is the trigger to reach for $\frac{1}{n+1}\binom{2n}{n}$ instead of brute-force enumeration.