Teaching Kids Programming: Videos on Data Structures and Algorithms

Introduction to Combinatorial Mathematics (2): Catalan Numbers

Catalan numbers are one of the most important sequences in combinatorics. They appear in many counting problems that look very different on the surface, but actually share the same underlying structure: balance, recursion, and non-crossing constraints.

In this post, we will introduce the Catalan numbers, show several important formulas, and explain some classic use cases, especially the grid-walking problem where a path is not allowed to cross the diagonal.

What Are Catalan Numbers?

The Catalan sequence begins as follows:

The general formula for the nth Catalan number is:

An equivalent form is:

These two formulas are completely equivalent and both appear often in combinatorics.

Why Catalan Numbers Matter

Catalan numbers count many kinds of recursive or balanced structures. They often appear when:

• objects must be built in a balanced way,
• paths must stay within a boundary,
• pairings cannot cross,
• a structure can be split into independent left and right parts.

That is why they show up in problems involving parentheses, trees, grids, polygons, and stack operations.

Some Important Catalan Formulas

Closed Form

Equivalent Difference Form

Recursive Formula

This recursive formula is very important. It says that if a structure of size n can be split into a left part of size i and a right part of size n-1-i, then the total number is obtained by summing over all possible splits.

Generating Function

Asymptotic Growth

This tells us that Catalan numbers grow very quickly, though still slightly slower than pure exponential growth of 4^n.

Classic Use Cases of Catalan Numbers

1. Valid Parentheses

A classic example is counting the number of valid expressions formed by n pairs of parentheses.

For n = 3, the valid expressions are:

((())) (()()) (())() ()(()) ()()() 

There are 5 of them, so:

The key idea is that at no point, while reading from left to right, can the number of closing parentheses exceed the number of opening parentheses.

2. Binary Tree Shapes

The number of different binary tree shapes with n nodes is also the nth Catalan number.

Why? Because once you choose a root, the remaining nodes are split into a left subtree and a right subtree. If the left subtree has i nodes, then the right subtree has n – 1 – i nodes. This leads directly to the recurrence:

This interpretation is especially useful in data structures, recursive algorithms, and parsing.

3. Triangulations of a Polygon

The number of ways to triangulate a convex polygon with n + 2 sides is:

For example, the number of ways to triangulate a pentagon is:

This is another non-crossing structure: the diagonals used in the triangulation are not allowed to intersect.

4. Stack Permutations

Catalan numbers also count valid push-pop sequences of a stack with n items, where no invalid pop is allowed before a corresponding push.

Again, the same balance condition appears.

5. Non-Crossing Handshakes or Pairings

Suppose 2n people sit around a round table, and each person shakes hands with exactly one other person, with the rule that the handshakes must not cross.

The number of such non-crossing pairings is:

This is another excellent example of a Catalan structure.

Grid Walking Without Crossing the Diagonal

Now let us look at one of the most visual and beautiful interpretations of Catalan numbers.

The Problem

Suppose you start at the point (0,0) on a square grid and want to reach the point (n,n).

At each step, you may move only:

• one step to the right, or
• one step upward.

Without any restriction, every path consists of exactly n right moves and n up moves, so the total number of such paths is:

This is because we only need to choose which n of the 2n moves are the right moves.

The Restriction

Now impose the condition that the path must never cross above the diagonal line:

This means that at every point along the path, the number of upward steps taken so far can never exceed the number of rightward steps taken so far.

The number of such restricted paths is exactly the Catalan number:

Why This Matches the Parentheses Problem

There is a direct correspondence:

• right step corresponds to an opening parenthesis,
• up step corresponds to a closing parenthesis.

A path that never crosses above the diagonal is exactly like a parentheses sequence in which, at every prefix, the number of closing parentheses never exceeds the number of opening parentheses.

So the grid-walking problem and the valid-parentheses problem are actually the same combinatorial structure in disguise.

Example: n = 3

From (0,0) to (3,3), the total number of unrestricted paths is:

But the number of paths that never cross above the diagonal is:

So only 5 of the 20 paths satisfy the condition.

The Reflection Principle Idea

A classical way to derive the Catalan formula is to count:

• all paths from (0,0) to (n,n), and then
• subtract the bad paths that cross above the diagonal.

The total number of paths is:

The number of bad paths can be shown, using a reflection argument, to be:

Therefore the number of good paths is:

And this simplifies to:

which is exactly the Catalan number.

A Small Table of Catalan Numbers

n	C_n
0	1
1	1
2	2
3	5
4	14
5	42
6	132
7	429
8	1430

How to Recognize a Catalan Problem

When solving a combinatorics problem, Catalan numbers often appear when you see one or more of the following clues:

• balanced expressions,
• valid prefixes,
• non-crossing pairings,
• paths constrained by a diagonal or boundary,
• recursive splitting into left and right parts.

Whenever a counting problem has a hidden balance condition, it is worth checking whether Catalan numbers are involved.

Conclusion

Catalan numbers are a perfect example of how different mathematical problems can share the same internal structure.

They count:

• valid parentheses sequences,
• binary tree shapes,
• polygon triangulations,
• non-crossing pairings,
• stack-valid sequences,
• grid paths that do not cross the diagonal.

Among these, the grid-walking interpretation is especially intuitive. Starting from a simple path-counting problem, the diagonal restriction transforms an ordinary binomial counting problem into one of the most famous sequences in combinatorics.

If you understand why the diagonal restriction leads to Catalan numbers, you have already grasped one of the central ideas of combinatorial mathematics: very different-looking objects can often be counted in exactly the same way.

Key Formulas Summary

–EOF (The Ultimate Computing & Technology Blog) —

2644 words
Last Post: Programming is not my wife's thing.
Next Post: Introducing ExamGPT - Your AI Test Coach