Counting & ProbabilityDifficulty 50-9534 tagged problems

Catalan Numbers

Catalan Numbers is the habit of counting balanced or non-crossing structures with the Catalan formula. In contest math, that habit turns a crowded setup into a relation the student can test, bound, count, or compute. MathGrit teaches it as a recognizable signal, a deliberate move, and a final translation back to the original question.

Practice this technique Match my level

The Key Result

$$C_n = \frac{1}{n+1}\binom{2n}{n} = \binom{2n}{n} - \binom{2n}{n+1}, \qquad C_0 = 1$$

The Catalan numbers $1, 1, 2, 5, 14, 42, \ldots$ count balanced, non-crossing, or nested structures such as valid parenthesizations and lattice paths that stay below the diagonal.

Why It Works

1
Count monotone lattice paths from $(0,0)$ to $(n,n)$ that never rise above the diagonal $y = x$; the total number of monotone paths is $\binom{2n}{n}$.
2
A path is 'bad' if it ever crosses above the diagonal, i.e. touches the line $y = x + 1$.
3
Reflecting a bad path across $y = x + 1$ after its first illegal step is a bijection onto all monotone paths from $(-1, 1)$ to $(n, n)$, which number $\binom{2n}{n+1}$.
4
Subtracting bad from total gives $C_n = \binom{2n}{n} - \binom{2n}{n+1} = \dfrac{1}{n+1}\binom{2n}{n}$ after simplification.

Worked Examples

Example 1

In how many ways can $3$ pairs of parentheses be arranged so that they are balanced (every prefix has at least as many '(' as ')')? Verify with the Catalan formula.

1
This is the $n = 3$ Catalan count. Compute $C_3 = \dfrac{1}{3+1}\binom{6}{3} = \dfrac{1}{4} \cdot 20 = 5$.
2
List them to confirm: $((()))$, $(()())$, $(())()$, $()(())$, $()()()$ — exactly $5$ balanced strings.
3
Sanity check the formula on neighbors: $C_2 = \tfrac{1}{3}\binom{4}{2} = \tfrac{6}{3} = 2$ and $C_4 = \tfrac{1}{5}\binom{8}{4} = \tfrac{70}{5} = 14$.

Answer:

$C_3 = 5$

Warm-up

In how many ways can a convex hexagon (a $6$-gon) be cut into triangles by drawing non-crossing diagonals (a triangulation)?

1
Triangulations of a convex $(n+2)$-gon are counted by the Catalan number $C_n$. A hexagon has $6 = n + 2$ sides, so $n = 4$.
2
Compute $C_4 = \dfrac{1}{4+1}\binom{8}{4} = \dfrac{1}{5}\cdot 70 = 14$.
3
So there are $14$ triangulations.

Answer:

$14$

Contest level

How many sequences of $4$ up-steps $(+1)$ and $4$ down-steps $(-1)$ have every partial sum $\ge 0$ (a 'ballot' / Dyck path condition)?

1
A sequence of $n$ up-steps and $n$ down-steps with all partial sums nonnegative is a Dyck path, counted by $C_n$. Here $n = 4$.
2
Compute $C_4 = \dfrac{1}{5}\binom{8}{4} = \dfrac{70}{5} = 14$.
3
(Equivalently this is the number of ways to match $4$ pairs of balanced parentheses.)

Answer:

$14$

Olympiad / Challenge

Establish the Catalan recurrence $C_{n+1} = \sum_{i=0}^{n} C_i\,C_{n-i}$ combinatorially, and use it to compute $C_4$ from $C_0, C_1, C_2, C_3$.

1
Model $C_{n+1}$ as the number of balanced strings of $n+1$ pairs of parentheses. In any such nonempty string, match the FIRST '(' with its partner ')'.
2
That matched pair splits the string as $(\,A\,)\,B$, where $A$ is a balanced string of $i$ pairs (inside) and $B$ is a balanced string of $n - i$ pairs (after), for some $0 \le i \le n$.
3
Since $A$ and $B$ are chosen independently, summing the product over the split point gives $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$.
4
With $C_0 = 1, C_1 = 1, C_2 = 2, C_3 = 5$: $C_4 = C_0 C_3 + C_1 C_2 + C_2 C_1 + C_3 C_0 = 1\cdot5 + 1\cdot2 + 2\cdot1 + 5\cdot1 = 14$.

Answer:

$C_4 = 14$ (recurrence verified)

Going Deeper

The Catalan numbers $C_n = \frac{1}{n+1}\binom{2n}{n}$ satisfy the convolution recurrence $C_{n+1} = \sum_{i=0}^{n} C_i C_{n-i}$ and have generating function $C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}$. They count a famous web of equinumerous objects: balanced parentheses, Dyck paths, binary trees with $n$ internal nodes, triangulations of an $(n+2)$-gon, non-crossing chord matchings of $2n$ points, and stack-sortable permutations.
Catalan appears on AIME whenever a structure must stay 'balanced' or 'non-crossing': valid parenthesization, mountain ranges / lattice paths below a diagonal, ways to associate a product, and ballot problems. Recognizing one of the canonical Catalan objects instantly gives the closed form without re-deriving the reflection argument.
Pitfall: mind the index — triangulating an $m$-gon uses $C_{m-2}$, NOT $C_m$, and Dyck paths of semilength $n$ use $C_n$. Also $\frac{1}{n+1}\binom{2n}{n}$ is always an integer, but only because $(n+1) \mid \binom{2n}{n}$; do not 'simplify' by canceling incorrectly. The equivalent form $\binom{2n}{n} - \binom{2n}{n+1}$ is handy when the $\frac{1}{n+1}$ factor is awkward.

Spot the Signal

Use it when objects must stay balanced — matched parentheses, non-crossing chords, monotonic lattice paths.
You can describe the hard part as counting balanced or non-crossing structures with the Catalan formula, but a direct attack starts producing clutter.
The problem rewards preserving structure instead of expanding, listing, or guessing too early.

Learn the Move

Start by recognizing the Catalan structure and applying $C_n = \frac{1}{n+1}\binom{2n}{n}$.
Name the relation that makes Catalan Numbers legal before doing computation.
Use the new relation to replace the messiest part of the problem with a cleaner one.
Translate the result back to the quantity the problem actually asks for.

Avoid These Traps

Using $\binom{2n}{n}$ without the $\frac{1}{n+1}$ correction, or miscounting $n$.
Applying Catalan Numbers because it sounds relevant, without checking the trigger first.
Stopping after spotting the technique instead of finishing the calculation or proof.

MathGrit Coach Note

If it must never go negative, it's probably Catalan.

Try it on:

Count a balanced or non-crossing configuration governed by the Catalan numbers.