Catalan Numbers and Ballot Problems

Catalan numbers

C_{n} = \frac{1}{n + 1} (n 2 n)

count an astonishing variety of combinatorial objects (balanced parentheses, lattice paths that stay weakly above a diagonal, triangulations of polygons, binary trees). They arise as the solution to ballot problems, which ask for the probability that one candidate stays ahead throughout the counting of votes. The sequence begins

1, 1, 2, 5, 14, 42, 132, \dots

. Studied by Euler (1750s), Catalan (1838), and named by Riordan; the ballot connection is due to Bertrand and Désiré André (1887).

The Catalan numbers form one of the most ubiquitous integer sequences in combinatorics, with over 200 known interpretations catalogued by Richard Stanley. Formally, $C_{n}$ counts the lattice paths from $(0, 0)$ to $(n, n)$ using unit right and up steps that never rise above the diagonal $y = x$ — equivalently, the number of ways to correctly match $n$ pairs of parentheses. They matter because problems from disparate fields — parsing expressions, counting tree structures, random walks, even certain quantum and polymer models — all reduce to the same recurrence. The surprising fact is that a quantity defined by a binomial coefficient divided by $n + 1$ always comes out as an integer, and that this single number governs the ballot problem: the probability candidate A is always strictly ahead of B when A finishes with $p$ votes and B with $q < p$ is exactly $\frac{p - q}{p + q}$ , independent of how large the totals are.

The Core Insight

Every Catalan structure is a sequence of "opening" and "closing" steps in which, reading left to right, the number of closings never exceeds the number of openings. Counting the bad sequences that violate this — and showing they biject with completely unconstrained sequences via a reflection — yields both the Catalan formula and the ballot theorem in one stroke. The reflection principle is the unifying engine of the entire topic.

Formal Statement

Catalan Numbers

The $n$ -th Catalan number, for $n \geq 0$ , is

C_{n} = \frac{1}{n + 1} (n 2 n) = \frac{( 2 n )!}{( n + 1 )! n !} .

⟳Start from the lattice-path count and subtract bad paths; the

\frac{1}{n + 1}

factor emerges from

(n 2 n) - (n - 1 2 n)

An equivalent product form and an explicit difference form are

C_{n} = k = 2 \prod n \frac{n + k}{k} = (n 2 n) - (n + 1 2 n) .

⟳Telescope the ratio

C_{n} / C_{n - 1}

; the difference form comes directly from the reflection count of bad paths.

Here $n$ is a non-negative integer; $(n 2 n)$ is the central binomial coefficient counting all monotone lattice paths from $(0, 0)$ to $(n, n)$ .

Dyck Path

A Dyck path of semilength $n$ is a lattice path from $(0, 0)$ to $(2 n, 0)$ using up steps $U = (1, 1)$ and down steps $D = (1, - 1)$ that never goes below the $x$ -axis. Writing $U = ($ and $D =)$ gives a string of $n$ balanced parenthesis pairs. The number of Dyck paths of semilength $n$ is $C_{n}$ .

Catalan Recurrence

The Catalan numbers satisfy, with $C_{0} = 1$ ,

C_{n + 1} = i = 0 \sum n C_{i} C_{n - i}, n \geq 0.

⟳A nonempty Dyck path decomposes uniquely as

U (path_{i}) D (path_{n - i})

, where

path_{i}

sits inside the first matched pair.

Equivalently, the generating function $C (x) = \sum_{n \geq 0} C_{n} x^{n}$ satisfies

x C (x)^{2} - C (x) + 1 = 0, C (x) = \frac{1 - 1 - 4 x}{2 x} .

⟳The convolution [3] is the coefficient form of

C = 1 + x C^{2}

; solve the quadratic, choosing the root analytic at

x = 0

Bertrand's Ballot Theorem

In an election where candidate A receives $p$ votes and candidate B receives $q$ votes with $p > q$ , the number of orderings of the $p + q$ ballots in which A is strictly ahead throughout the count is

N = \frac{p - q}{p + q} (p p + q),

so the probability of A leading throughout a uniformly random count is

P = \frac{p - q}{p + q} .

⟳The total number of orderings is

(p p + q)

; subtract the "tied at some point" orderings counted by the reflection principle.

Why It Holds / Derivation

Reflection Principle for the Ballot Theorem

We count vote orderings as lattice paths. Encode an A-vote as $+ 1$ and a B-vote as $- 1$ ; the partial sum after $k$ votes is the running margin. A path runs from $(0, 0)$ to $(p + q, p - q)$ .

Step 1. The total number of such paths (orderings) is

(p p + q)

, choosing positions for the

p

A-votes. Step 2. "A strictly ahead throughout" means the path's partial sum is

\geq 1

for all

k \geq 1

. Since the first vote must give A the lead, it is an A-vote, reaching

(1, 1)

. We must count paths from

(1, 1)

(p + q, p - q)

that never touch the line

y = 0

. Step 3. Count the bad paths from

(1, 1)

to the endpoint that do touch

y = 0

. By the reflection principle, reflect the initial segment up to the first contact with

y = 0

across the

x

-axis. This bijects bad paths from

(1, 1)

with all paths from

(1, - 1)

(p + q, p - q)

. Step 4. A path from

(1, - 1)

(p + q, p - q)

has horizontal length

p + q - 1

and net rise

(p - q) - (- 1) = p - q + 1

. The number of up steps

a

and down steps

b

satisfy

a + b = p + q - 1

and

a - b = p - q + 1

, giving

a = p

b = q - 1

. Thus there are

(q - 1 p + q - 1)

bad paths. Step 5. Paths from

(1, 1)

to the endpoint number

(p - 1 p + q - 1) = (q p + q - 1)

. Subtracting the bad ones:

N = (q p + q - 1) - (q - 1 p + q - 1) .

⟳This is the "good minus reflected bad" count; simplify the factorials next.

Step 6. Combine using

(q p + q - 1) = \frac{p}{p + q} (q p + q)

and

(q - 1 p + q - 1) = \frac{q}{p + q} (q p + q)

N = \frac{p - q}{p + q} (q p + q) = \frac{p - q}{p + q} (p p + q) .

⟳Factor out

\frac{1}{p + q} (q p + q)

and combine the numerators

p - q

Dividing by the total $(p p + q)$ gives $P = \frac{p - q}{p + q}$ . $■$

From the Ballot Theorem to the Catalan Formula

Set $q = n$ and $p = n + 1$ in the weak-lead variant (A always $\geq$ B). A Dyck path of semilength $n$ corresponds to a vote sequence where A never trails. By the standard "tie-allowed" ballot count, the number of paths from $(0, 0)$ to $(2 n, 0)$ staying $\geq 0$ is

C_{n} = (n 2 n) - (n - 1 2 n) = \frac{1}{n + 1} (n 2 n) .

⟳

(n - 1 2 n) = \frac{n}{n + 1} (n 2 n)

, so the difference equals

\frac{1}{n + 1} (n 2 n)

The bad paths (those dipping below $0$ ) reflect across $y = - 1$ into unconstrained paths from $(0, - 2)$ to $(2 n, 0)$ , of which there are $(n - 1 2 n)$ . $■$

Eugène Charles Catalan | 1814–1894

Belgian-French mathematician, a student of Joseph Liouville, who worked extensively on continued fractions, number theory, and combinatorics. In 1838 he investigated the number of ways to dissect a convex polygon into triangles by non-crossing diagonals, deriving the numbers now bearing his name. He also posed Catalan's conjecture (that $8$ and $9$ are the only consecutive perfect powers), proved only in 2002 by Mihăilescu. The naming "Catalan numbers" was popularized by John Riordan in the 20th century, though Euler had found the polygon-triangulation count nearly a century earlier and the Mongolian mathematician Minggatu had studied related series even before.

Building Intuition

Picture stacking and unstacking plates. An up step puts a plate on the stack; a down step removes one. A valid sequence (a Dyck path) never tries to remove a plate from an empty stack. The Catalan number $C_{n}$ counts how many ways you can do $n$ pushes and $n$ pops without ever popping an empty stack — exactly the legal sequences of stack operations, exactly the balanced parenthesizations, exactly the binary tree shapes.

The ballot problem is the probabilistic face of the same picture: if A leads with $p$ to $q$ , the "fraction of the lead" $\frac{p - q}{p + q}$ is precisely the chance the lead held the entire time. Notice the elegance: the answer depends only on the final margin relative to the total, not on the individual sizes. A landslide $1000$ -to- $0$ gives probability $1$ ; a squeaker $51$ -to- $49$ gives $\frac{2}{100}$ — a mere $2%$ chance A never once let B catch up.

A Dyck path of semilength 4 and its reflection of a bad path

Worked Examples

Triangulating a Pentagon

Given. Count the ways to divide a convex pentagon (5 vertices) into triangles using non-crossing diagonals. Steps. A convex

(n + 2)

-gon triangulation count equals

C_{n}

. A pentagon has

n + 2 = 5

, so

n = 3

C_{3} = \frac{1}{3 + 1} (3 6) = \frac{1}{4} \cdot 20 = 5.

⟳Plug

n = 3

into [1];

(3 6) = 20

Each triangulation uses $n - 1 = 2$ diagonals and produces $n = 3$ triangles. Listing them: fix the base edge and choose which vertex forms a triangle with it — the recurrence $C_{3} = C_{0} C_{2} + C_{1} C_{1} + C_{2} C_{0} = 2 + 1 + 2 = 5$ confirms it.

Answer.

5 triangulations

(dimensionless count).

A Concrete Ballot Count

Given. Candidate A gets

p = 7

votes, candidate B gets

q = 3

votes; ballots are counted in uniformly random order. Find the number of count orderings in which A is strictly ahead at every step, and the probability. Steps. Total orderings:

(7 10) = 120

. Apply [5]:

N = \frac{p - q}{p + q} (p p + q) = \frac{7 - 3}{7 + 3} (7 10) = \frac{4}{10} \cdot 120 = 48.

⟳

\frac{p - q}{p + q} = \frac{4}{10} = 0.4

; multiply by

120

The probability is

P = \frac{p - q}{p + q} = \frac{4}{10} = 0.4 = 40%.

⟳This is [6] directly; equals

N /120 = 48/120

Answer.

N = 48 favourable orderings, P = 40%

Common Misconceptions

"Strictly ahead" and "never behind (ties allowed)" give different counts. The strict ballot theorem yields

\frac{p - q}{p + q} (p p + q)

, while the weak version (A never trails, ties permitted) yields the larger count

\frac{p - q + 1}{p + 1} (p p + q)

. Catalan numbers correspond to the weak version with

p = q

adjusted to

p = n + 1, q = n

in the path setup. Confusing the two off-by-one variants is the single most common error in this topic. The formula $\frac{p - q}{p + q}$ is NOT the probability that A wins. A wins with certainty here (we are told

p > q

). The quantity

\frac{p - q}{p + q}

is the conditional probability that A led the entire count given the final tallies. Suppose someone reasons: "A got 60% of votes, so A should lead the count 60% of the time." With

p = 6, q = 4

, the true probability of leading throughout is

\frac{6 - 4}{6 + 4} = 0.2

, not

0.6

. The intuition that "vote share equals lead-probability" is flatly wrong.

Connections

Catalan numbers tie together a remarkable web of structures. They equal the number of Binary Trees with $n$ internal nodes, the number of non-crossing partitions of ${1, \dots, n}$ , and the dimension of certain invariant spaces in Representation Theory. The defining quadratic generating function [4] links them to Generating Functions and the Lagrange inversion formula. The reflection-principle proof is the discrete analogue of the Reflection Principle for Brownian Motion, where the ballot theorem becomes the arcsine law and the distribution of the maximum of a random walk. The recurrence [3] is a convolution, foreshadowing the role of Catalan numbers in Free Probability as the moments of the semicircle distribution.

Real-World Applications

Compiler design / parsing. The number of valid ways to fully parenthesize an expression with $n + 1$ factors (or to build a parse tree) is $C_{n}$ ; this governs the size of expression-evaluation search spaces in matrix-chain multiplication dynamic programming.
RNA secondary structure prediction. Counting non-crossing base pairings in a strand reduces to Catalan-type recurrences (Nussinov algorithm), bounding the conformational state space.
Random walks and queueing. The ballot theorem gives the exact distribution of the time a random walk spends positive, central to M/M/1 queue busy-period analysis and ruin probabilities in actuarial mathematics.
Quantitative finance. First-passage and barrier-option pricing on binomial trees uses reflection-principle counts directly descended from the ballot problem.
Algorithm analysis. The number of distinct shapes of a stack-sortable permutation and the number of valid sequences of $n$ push/pop operations are both $C_{n}$ — relevant to data-structure complexity proofs.
Statistical physics / polymers. Dyck paths model directed lattice polymers near a wall; Catalan asymptotics $C_{n} \sim \frac{4 ^{n}}{n ^{3/2} π}$ give the partition-function scaling.
Phylogenetics. Counting rooted binary tree topologies on $n + 1$ leaves yields $C_{n}$ , fixing the search space for tree-reconstruction algorithms.

Historical Development

1730s–1750s. Minggatu (Ming Antu) in China studies infinite series whose coefficients are essentially Catalan numbers, in work on trigonometric expansions.
1751. Leonhard Euler, in correspondence with Christian Goldbach, finds the formula for triangulating convex polygons — the first explicit appearance of the sequence in the West.
1758–1759. Johann Andreas von Segner gives the recurrence [3] for polygon triangulations; Euler conjectures the closed product form.
1838. Eugène Catalan studies the number of ways to parenthesize a product and connects it to the polygon problem, establishing the modern context.
1887. Joseph Bertrand poses the ballot problem; Désiré André publishes the elegant reflection-principle solution within weeks, the first appearance of the reflection method.
1923. J. Aebly and D. Mirimanoff refine the reflection argument into its now-standard bijective form.
Mid-20th century. John Riordan and others systematize the sequence; the name "Catalan numbers" becomes standard.
1999–2015. Richard Stanley compiles over 200 combinatorial interpretations in Enumerative Combinatorics and the monograph Catalan Numbers.
2002. Preda Mihăilescu proves Catalan's conjecture on consecutive perfect powers (a separate result, but cementing Catalan's name in two domains).

Subtleties & Limits

While the closed form and recurrence are completely understood, Catalan-related enumerations remain a fertile research frontier. Open and active areas include: (1) the cyclic sieving phenomenon — explaining why $C_{n}$ and its $q$ -analogue track symmetries of Catalan objects under rotation, with many conjectured instances still unproven; (2) classifying which generalizations (Fuss–Catalan numbers $\frac{1}{mn + 1} (n mn + 1)$ , rational Catalan numbers $\frac{1}{a + b} (a a + b)$ for coprime $a, b$ ) admit clean bijective proofs; (3) understanding $q, t$ -Catalan numbers from the theory of diagonal harmonics, where positivity conjectures of Garsia–Haiman drove decades of work in algebraic combinatorics. The interplay between the analytic, algebraic, and bijective faces of these numbers continues to generate problems despite the elementary appearance of [1].