Catalan Numbers and Balanced Structures

How many ways can you correctly balance three pairs of parentheses, like ()()(), (())(), ((())), ()(()), and (()())? By hand, listing them out for $n=3$ gives exactly 5. For $n=4$ pairs it's 14; for $n=10$ pairs it's 16,796. There's no obvious way to see that pattern by brute-force listing, but it turns out to be one specific, famous sequence — the Catalan numbers — and the same sequence answers a surprising range of interview questions that don't look related to parentheses at all: valid push/pop sequences on a stack, ways a stock's cumulative return can stay non-negative over a sequence of up/down ticks, and non-crossing ways to pair up points on a circle.

The formula, one symbol at a time

The $n$-th Catalan number is:

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

In plain English: take the number of unrestricted lattice paths with $n$ right-moves and $n$ up-moves ($\binom{2n}{n}$, from ordinary path-counting), then divide by $n+1$ to correct for the fraction of those paths that break the "balanced" constraint — a correction derived from a clever reflection argument, not something to re-derive from scratch in an interview. What matters for recognizing when to use it: $C_n$ counts exactly the sequences of $n$ "up" symbols and $n$ "down" symbols such that, read left to right, the running total of ups minus downs never goes negative.

Worked example 1: balanced parentheses for n=3

$C_3 = \dfrac{1}{4}\binom{6}{3} = \dfrac{1}{4}\times20 = 5$, matching the five listed by hand above. Each ( is an "up" step and each ) is a "down" step; a string is validly balanced exactly when, reading left to right, you never have more closes than opens so far — the same non-negative-running-total condition the formula encodes.

Worked example 2: a stock price that never goes negative

A stock starts at $0 and over 4 ticks moves either +$1 or −$1 each tick, ending back at $0 (so exactly 2 up-ticks and 2 down-ticks). How many tick sequences keep the price at or above $0 the entire time? This is exactly $C_2 = \dfrac{1}{3}\binom{4}{2} = \dfrac{1}{3}\times6=2$. Listing them confirms it: UUDD and UDUD both stay non-negative throughout (checking running totals: $1,2,1,0$ and $1,0,1,0$), while UDDU and DUUD and DDUU all dip below zero at some point and are excluded. Recognizing "never goes negative" as the Catalan signature turns a case-by-case enumeration into a two-step formula.