The Problem Pit: The Pit of Lattice Paths

The Pit of Lattice Paths: Counting Without Crossing

Some math problems are honest about their difficulty. You look at the Riemann Hypothesis, and it immediately feels intimidating. But lattice paths? Counting walks on a grid? That sounds like something for children.

That’s what I thought, at least. Then I stepped in.

---

Step 1: The Innocent Beginning

The basic question:

How many shortest paths are there from $(0,0)$ to $(n,n)$ if you can only move right ($R$) or up ($U$)?

At first this feels like shuffling cards. You need $n$ rights and $n$ ups. That’s $2n$ moves in total, arranged in some order.

So the answer is just

$$\binom{2n}{n}.$$

For $n=3$: $\binom{6}{3} = 20$.

Easy! Problem solved.

…Or so I thought.

---

Step 2: Adding a Wall

What if I require the path to never go above the diagonal? That is, at every point, the path must satisfy $y \leq x$.

This tiny change sends the problem spiraling.

Take $n=3$: there are 20 total paths. How many stay below the diagonal? Draw them, count carefully… and the answer is 5.

That number felt too neat. For $n=4$, it’s 14. For $n=5$, it’s 42.

Then the pattern hits:

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

I recognized it. The infamous Catalan numbers.

---

Step 3: The Catalan Trap

Catalan numbers are defined by

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

So the number of lattice paths from $(0,0)$ to $(n,n)$ that never cross the diagonal is $C_n$.

Neat. I should’ve been happy.

Instead, I got stuck.

Because Catalan numbers appear everywhere. Once you see them, you can’t unsee them:

• Number of ways to correctly parenthesize $n+1$ terms.

• Number of binary trees with $n$ nodes.

• Number of noncrossing matchings on $2n$ points.

• Number of monotone lattice paths under a diagonal.

And each of these interpretations can be proved to be the same number.

I thought: surely there’s some “master proof” that explains them all. I tried to invent one. I failed. I drowned in bijections.

---

Step 4: Wrong Turns

I tried to solve the diagonal restriction problem directly with algebra.

The condition $y \leq x$ suggests inequalities. Maybe I could sum binomial coefficients over constrained regions. I wrote:

$$\# \{ \text{valid paths} \} = \sum_{k=0}^n f(k),$$

where $f(k)$ counts something. I never managed to close the formula.

Then I tried recursion: a valid path either starts with $R$ then a smaller valid path, or splits into two pieces at the diagonal. This gave the recurrence

$$C_{n+1} = \sum_{i=0}^n C_i C_{n-i}.$$

That was progress. But the recurrence just felt like a trick, not an explanation. Why should lattice paths multiply like this?

Another dead end.

---

Step 5: Generating Function Madness

I decided to try generating functions:

$$C(x) = \sum_{n=0}^\infty C_n x^n.$$

The recurrence suggested

$$C(x) = 1 + x C(x)^2.$$

That’s a quadratic equation! Solve it:

$$C(x) = \frac{1 - \sqrt{1 - 4x}}{2x}.$$

And expanding the square root recovers

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

At first I was satisfied. But then I wondered: why does a lattice path problem lead to a generating function involving a square root? What’s hiding behind that radical?

I dug deeper.

---

Step 6: The Ballot Problem Detour

I realized the diagonal restriction is just the Ballot problem:

If candidate A gets $p$ votes and candidate B gets $q$ votes, how many ways can the votes be counted so that A is never behind?

The answer:

$$\frac{p-q+1}{p+1} \binom{p+q}{q}.$$

For $p=q=n$, this reduces to the Catalan number $C_n$.

Suddenly, a lattice path became a political election. But this was no help — it just gave me another disguise of the same beast.

---

Step 7: Catalan Everywhere

The pit deepened. I kept stumbling on Catalan numbers in unexpected places:

• Number of ways to triangulate a convex $(n+2)$-gon.

• Number of stack-sortable permutations of length $n$.

• Number of non-crossing partitions of a set.

• Number of ways to dissect a staircase polyomino.

I realized: Catalan numbers are not just about paths. They are a universal combinatorial skeleton.

But why? I still didn’t have my master proof.

---

Step 8: Asymptotics and Analysis

Finally, I wondered: how fast do Catalan numbers grow?

Using Stirling’s approximation on

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

I found

$$C_n \sim \frac{4^n}{n^{3/2} \sqrt{\pi}}.$$

So they grow like $4^n$, but with a polynomial suppression.

That made sense: the total number of paths is $\binom{2n}{n} \sim \frac{4^n}{\sqrt{\pi n}}$. Requiring the path to stay under the diagonal is a “rare event” with probability about $1/(n+1)$.

Probability snuck in. Now lattice paths had turned into random walks.

---

Step 9: The Random Walk Abyss

I thought: a path from $(0,0)$ to $(n,n)$ is just a sequence of coin flips. Heads = right, tails = up. The condition “stay below the diagonal” means the walk never falls behind.

That’s exactly the reflection principle in probability. And Catalan numbers are just counting paths that don’t violate it.

So this innocent problem wasn’t just combinatorics. It was also probability theory, random walks, and Brownian motion.

---

Step 10: Climbing Out (Almost)

In the end, I realized:

• Lattice paths under a diagonal are Catalan numbers.

• Catalan numbers connect trees, polygons, elections, stack sorting, and more.

• Their generating function hides a square root, signaling deep structure.

• Their asymptotics connect to probability and random walks.

I went in expecting to count paths on a grid. I came out knowing I had been staring at one of the most universal sequences in mathematics.

That’s what The Problem Pit does: it takes a child’s puzzle and reveals a monster that touches every corner of math.

---