Catalan Numbers and Ballot Problems

⚡ Key Takeaways

Catalan numbers $C_n = \frac{1}{n+1}\binom{2n}{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 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.

DefinitionCatalan Numbers

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

1

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

Derivation hint: Start from the lattice-path count and subtract bad paths; the $\frac{1}{n+1}$ factor emerges from $\binom{2n}{n}-\binom{2n}{n-1}$ . An equivalent product form and an explicit difference form are

2

\quad C_n = \prod_{k=2}^{n}\frac{n+k}{k} = \binom{2n}{n}-\binom{2n}{n+1}.

Derivation hint: 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; $\binom{2n}{n}$ is the central binomial coefficient counting all monotone lattice paths from $(0,0)$ to $(n,n)$ .

DefinitionDyck Path

A Dyck path of semilength $n$ is a lattice path from $(0,0)$ to $(2n,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$ .

TheoremCatalan Recurrence

The Catalan numbers satisfy, with $C_0 = 1$ ,

3

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

Derivation hint: A nonempty Dyck path decomposes uniquely as $U\,(\text{path}_i)\,D\,(\text{path}_{n-i})$ , where $\text{path}_i$ sits inside the first matched pair. Equivalently, the generating function $C(x) = \sum_{n\ge 0} C_n x^n$ satisfies

4

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

Derivation hint: The convolution [3] is the coefficient form of $C = 1 + xC^2$ ; solve the quadratic, choosing the root analytic at $x=0$ .

TheoremBertrand'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

5

\quad N = \frac{p-q}{p+q}\binom{p+q}{p},

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

6

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

Derivation hint: The total number of orderings is $\binom{p+q}{p}$ ; subtract the "tied at some point" orderings counted by the reflection principle.

ProofReflection 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 $\binom{p+q}{p}$ , choosing positions for the $p$ A-votes.

Step 2. "A strictly ahead throughout" means the path's partial sum is $\ge 1$ for all $k \ge 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)$ to $(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)$ to $(p+q,p-q)$ .

Step 4. A path from $(1,-1)$ to $(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 $\binom{p+q-1}{q-1}$ bad paths.

Step 5. Paths from $(1,1)$ to the endpoint number $\binom{p+q-1}{p-1} = \binom{p+q-1}{q}$ . Subtracting the bad ones:

7

\quad N = \binom{p+q-1}{q} - \binom{p+q-1}{q-1}.

Derivation hint: This is the "good minus reflected bad" count; simplify the factorials next.

Step 6. Combine using $\binom{p+q-1}{q} = \frac{p}{p+q}\binom{p+q}{q}$ and $\binom{p+q-1}{q-1} = \frac{q}{p+q}\binom{p+q}{q}$ :

8

\quad N = \frac{p-q}{p+q}\binom{p+q}{q} = \frac{p-q}{p+q}\binom{p+q}{p}.

Derivation hint: Factor out $\frac{1}{p+q}\binom{p+q}{q}$ and combine the numerators $p - q$ . Dividing by the total $\binom{p+q}{p}$ gives $P = \frac{p-q}{p+q}$ . $\blacksquare$

∎

ProofFrom the Ballot Theorem to the Catalan Formula

Set $q = n$ and $p = n+1$ in the weak-lead variant (A always $\ge$ 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 $(2n,0)$ staying $\ge 0$ is

9

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

Derivation hint: $\binom{2n}{n-1} = \frac{n}{n+1}\binom{2n}{n}$ , so the difference equals $\frac{1}{n+1}\binom{2n}{n}$ . The bad paths (those dipping below $0$ ) reflect across $y=-1$ into unconstrained paths from $(0,-2)$ to $(2n,0)$ , of which there are $\binom{2n}{n-1}$ . $\blacksquare$

∎

mathematician · 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.

🧠 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.

Figure

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

ExampleTriangulating 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$ .

10

\quad C_3 = \frac{1}{3+1}\binom{6}{3} = \frac{1}{4}\cdot 20 = 5.

Derivation hint: Plug $n=3$ into [1]; $\binom{6}{3}=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_0C_2 + C_1C_1 + C_2C_0 = 2 + 1 + 2 = 5$ confirms it.

Answer. $\boxed{5 \text{ triangulations}}$ (dimensionless count).

ExampleA 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: $\binom{10}{7} = 120$ . Apply [5]:

11

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

Derivation hint: $\frac{p-q}{p+q} = \frac{4}{10} = 0.4$ ; multiply by $120$ . The probability is

12

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

Derivation hint: This is [6] directly; equals $N/120 = 48/120$ .

Answer. $\boxed{N = 48 \text{ favourable orderings}, \quad P = 40\%}$ .

⚠️ Common mistake

"Strictly ahead" and "never behind (ties allowed)" give different counts. The strict ballot theorem yields $\frac{p-q}{p+q}\binom{p+q}{p}$ , while the weak version (A never trails, ties permitted) yields the larger count $\frac{p-q+1}{p+1}\binom{p+q}{p}$ . 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.

Counterexample

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.

connection

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.

🔬 Where this appears

⏳ History

- 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).

open-problem

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}\binom{mn+1}{n}$ , rational Catalan numbers $\frac{1}{a+b}\binom{a+b}{a}$ 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].

Formal Statement

Why It Holds / Derivation

Building Intuition

Worked Examples

Common Misconceptions

Connections

Real-World Applications

Historical Development

Subtleties & Limits

See Also