252 Staircase Paths, and the Word That Replaces the Grid

Start at the bottom left corner of a five by five grid and walk to the opposite corner. Every step goes one unit east or one unit north. Never west, never south, never diagonally. How many different routes are there?

The instinctive move is to start drawing, and the instinctive move after that is to give up and multiply something. Neither is needed. The count is $\binom{10}{5} = 252$, and the reason is one change of notation that makes the geometry disappear.

Every route has the same length

Whatever route you take, you finish five columns to the right and five rows up. East steps only ever move you right and north steps only ever move you up, so you need exactly five of each. Ten steps, no exceptions, no shorter or longer routes to worry about.

That single observation is what makes the problem finite in a useful way. A route is now a sequence of ten decisions, and each decision is a letter: $E$ or $N$. The route drawn in figure 1 is the word $ENNEENENNE$.

The move: routes are words

Both directions of that statement need saying. A route gives a word with five $E$s because it has to end at $(5,5)$. A word with five $E$s gives a route that arrives, because after all ten letters you have moved five east and five north whatever order they came in. There is no third thing that is a word but not a route, and no route left over without a word.

Counting words with five $E$s is choosing which five of the ten slots are east. And that is a binomial coefficient:

Where 1024 comes from

The common wrong answer is $2^{10} = 1024$, and it is worth taking seriously because the arithmetic behind it is correct. Ten steps with two free choices each really does give 1024 possibilities. The trouble is that most of those walks never reach the far corner. Ten easts in a row is one of the 1024, and it walks off the right edge of the grid and keeps going along the bottom.

So 772 of the ten-step walks end somewhere other than $(5,5)$, and slightly fewer than a quarter of them arrive. The reflex answer is the exact solution to a question that never mentioned a destination.

A second count that shares no step with the first

Fill the grid in instead. Write 1 at the start. At any other lattice point, the routes reaching it arrive either from the point below or from the point to its left, and those two families never overlap, so the count at each point is the sum of the two counts behind it.

The corner comes out at 252 again, which is the check worth doing because the two derivations share nothing but the answer. The grid is also a rotated slab of Pascal's triangle: $252$ is the middle entry of the tenth row, and it is the largest entry in that row. The row sums to $1024$, which is the same 1024 as before, now correctly described as the total over all endpoints rather than the count at one of them.

Any rectangle, and how big these numbers get

Nothing in the argument cared about the number five. On an $m$ by $n$ grid a route has $m+n$ steps of which $m$ are east:

For a square grid this is the central binomial coefficient $\binom{2n}{n}$, which grows like $4^n/\sqrt{\pi n}$. At $n = 5$ that approximation gives 258.4 against the true 252, already within three per cent. The practical consequence is that enumeration is hopeless very early. A ten by ten grid has 184,756 routes and a twenty by twenty grid has about $1.4 \times 10^{11}$.

In three dimensions the same argument gives a multinomial coefficient. Walking to $(5,5,5)$ takes fifteen steps split five ways in each direction, so there are $15!/(5!)^3 = 756{,}756$ routes.

Where the formula stops working

Equation (3) counts routes with no obstructions. Add one constraint and the binomial is no longer the answer, though it usually stays the starting point.

Forbid a single point and you subtract the routes through it. Routes through $(2,2)$ number $\binom{4}{2}\binom{6}{3} = 6 \cdot 20 = 120$, since a route through a point is a route to it followed by a route from it. So 132 of the 252 routes avoid $(2,2)$.

Forbid a whole region and the count changes character. Ask for routes that never rise above the diagonal, meaning you are never north of east, and the answer is a Catalan number:

Forty-two of the 252, exactly one sixth. The $1/(n+1)$ factor is not something you would guess from the unconstrained count, and it needs a different argument entirely, usually a reflection that pairs up the bad routes with routes to a shifted endpoint. That is the honest boundary of the trick in this article: turning geometry into words works beautifully while the only condition is where you finish, and it needs help the moment the condition is about where you have been.

Sources and further reading

• The objects being counted — Lattice path
• The coefficient in equation (1), and the recursion in figure 2 — Binomial coefficient and Pascal's triangle
• What happens under the diagonal constraint — Catalan number

The headline was checked exhaustively rather than by formula: all 1024 ten-letter words were generated, each was walked on the grid, and exactly 252 finished at $(5,5)$. The lattice recursion and the factorial evaluation agree, and the correspondence in the definition box was verified in both directions rather than assumed.