Every entry counts the routes to it

A binomial coefficient counts choices, and there is a second thing it counts that turns every identity about it into a picture. Lay out a grid of streets. Start at one corner and walk to another, going only right and only up. How many routes are there?

Thirty-five, which is $\binom{7}{3}$. The reason is immediate once stated: a route is seven steps long, three of them go up, and choosing the route is choosing which three of the seven steps go up. A route is a subset, and the correspondence is exact rather than approximate.

The triangle, rotated #

Every number in that grid is an entry of Pascal’s triangle, and the grid is the triangle turned forty-five degrees.

The corner $i$ steps right and $j$ steps up holds $\binom{i+j}{j}$. Rows of the triangle are anti-diagonals of the grid — the corners at a fixed total number of steps — and the triangle’s additive rule, which the rung below reads as a running total, is the grid’s, because a route reaching a corner arrives on its last step either from the left or from below.

That is the additive rule with a reason attached. In the triangle it is a rule about numbers: each entry is the sum of the two above. In the grid it is a classification: every route to a corner is a route to one of the two corners behind it, followed by one step, and the two cases do not overlap because a route has exactly one last step.

The two readings are the same statement and only the second explains anything. A reader who has met the triangle as an arrangement can verify the rule; a reader who has met the grid knows why no other rule was possible.

Cutting the routes in one place #

The route reading turns identities into arguments about where a route is when. The most useful of them comes from cutting the grid along one anti-diagonal.

A route to the far corner is seven steps. After four of them it is somewhere on the anti-diagonal $i + j = 4$, at exactly one corner, and the corner it is at determines nothing about the rest of the journey. So the routes split into groups by crossing point, and each group has (routes to that corner) times (routes onward from it) members.

Writing it out gives

$$\sum_j \binom{m}{j}\binom{n}{k-j} = \binom{m+n}{k},$$

which is Vandermonde’s identity, and the picture is the whole proof. The left-hand side is the sum over crossing points; the right-hand side is the total; and the two count the same routes.

The algebraic proof of the same identity is a comparison of coefficients in $(1+x)^m(1+x)^n = (1+x)^{m+n}$, which is correct, short, and says nothing about why the sum has that shape. The route argument says exactly why: it is a sum over the ways of splitting a journey into two legs.

A sum of products of that shape is called a convolution, and it appears whenever two independent things are combined and the total of some quantity is fixed. Vandermonde’s identity is the statement that binomial coefficients convolve into binomial coefficients, and it is the reason the count of heads in two independent runs of coin flips behaves like a single longer run.

The identities from the rung below, re-read #

Every sum on the previous rung has a route proof, and the route proofs are the ones worth remembering.

The stick. A run down a diagonal adds to an entry one row down and one along. In route terms: classify the routes to a corner by how far along the last upward step happens. Once the last upward step is fixed, everything after it is forced — the route goes right the rest of the way — and everything before it is a route to a smaller corner. The classes are the entries of the run.

The row sum. All the corners at a fixed distance from the start, taken together, hold every route of that length — because a route of $n$ steps ends somewhere on the $n$-th anti-diagonal, and each step is a free binary choice. So the anti-diagonal adds to $2^n$.

The squares. $\sum_k \binom{n}{k}^2 = \binom{2n}{n}$ is Vandermonde with $m = n$ and $k = n$, and the picture is a square grid cut down its own middle diagonal. The symmetry that turns the product into a square is the fact that a route to a middle corner from the far end is a route from the near end read backwards.

Three identities, one picture apiece, and the pictures are all the same picture cut in different places.

What the reading buys past the identities #

The route picture is not only a proof technique. It changes what questions are natural.

Routes that avoid something. Ask for the routes that never rise above the diagonal and the count is a Catalan number rather than a binomial one; ask for the routes avoiding a particular corner and the count is a difference of products. Neither question is expressible in the language of choices without a translation, and both are obvious in the language of routes.

The reflection argument. Routes that touch a forbidden line can be counted by reflecting the part of the route before the first touch, which turns them into routes to a different corner. Counting the paths that go wrong is that argument in full, and the path folded at its first touch is the same reflection asked of a random walk one field away. It has no expression at all in the language of subsets.

And the walk. A route chosen uniformly at random is a random walk that takes $n$ steps, and the corner it ends at is distributed like the number of heads in $n$ coin flips. That is why the balls falling through a peg board land in a bell shape: each ball is a route, the routes to a bin are the entries of a row, and the row is what the triangle holds.

Counting the routes that avoid a corner #

The reading earns its place on a question the choice reading cannot state, and the smallest such question is worth working through.

How many routes from one corner of the grid to the other avoid a particular intermediate corner? Every route either passes through it or does not, and the ones that pass through it are counted by the same split as Vandermonde: routes to the forbidden corner, times routes onward. So the answer is a subtraction,

$$\binom{a+b}{b} - \binom{i+j}{j}\binom{(a-i)+(b-j)}{b-j},$$

and there is nothing to it once the routes are in view. Stated in the language of subsets it is a claim about which subsets have a particular property at a particular position, and it takes a paragraph to even say.

Forbidding several corners needs inclusion–exclusion over them, with a term for each subset of the forbidden set, signed. That is the general method and it is expensive: forbidding twenty corners means a thousand-term alternating sum, and the terms are large and nearly cancel.

Which is where the picture stops being merely a proof technique and becomes an algorithm. Rather than the alternating sum, fill the grid by the additive rule with the forbidden corners set to nought. Every count is then built from its two neighbours as before, the forbidden corners contribute nothing to anything downstream, and the answer appears at the far corner after one pass. It costs one addition per corner, whatever the number of obstacles, against an exponential sum.

That is the same manoeuvre as the sieve run forwards instead of backwards, and it is a fair general lesson: an inclusion–exclusion over obstacles is often a signal that the object should be built up rather than corrected afterwards. The additive rule was there all along; what the obstacles change is only the initial values.

Where the coefficients sit relative to each other #

One more thing falls out of the grid, and it is the fact that makes the row a bell shape.

Walk along an anti-diagonal, comparing consecutive entries. The ratio of $\binom{n}{k+1}$ to $\binom{n}{k}$ is $(n-k)/(k+1)$, which is above one while $k < (n-1)/2$ and below one after — so the entries rise, reach a maximum in the middle, and fall, and the maximum is at $k = n/2$ or the two entries either side of it when $n$ is odd.

In route terms that is a statement about where the corners with the most routes are, and the answer is the middle of the anti-diagonal: a corner near the edge is reachable only by routes that commit early, and a corner in the middle by routes that can distribute their upward steps anywhere.

The ratio also says how sharply the entries fall. Two steps from the middle the ratio has moved by about $4/n$, so the profile near the peak is a product of factors each close to one, and the logarithm of the entry is a sum of small terms — which is a quadratic in the displacement from the middle. A quadratic in the exponent is a bell curve, and that is the whole of why the row of Pascal’s triangle looks the way it does, before any limit is taken.

The correspondence, stated carefully #

It is worth writing out the bijection precisely, because “a route is a subset” is doing all the work and a loose version of it would be wrong.

A route from $(0,0)$ to $(a, b)$ consists of $a + b$ steps, of which exactly $b$ are upward. Write the route as a word in two letters — R for right, U for up — and it is a word of length $a+b$ with exactly $b$ U’s. Conversely any such word is a route: reading it off from the start produces a sequence of moves that stays inside the grid precisely because the U count never exceeds $b$ and the R count never exceeds $a$, both guaranteed by the letter counts.

So routes and words are in one-to-one correspondence, and words with $b$ U’s correspond to the $b$-element subsets of the positions $1, \ldots, a+b$. Two bijections, composed, and $\binom{a+b}{b}$ counts all three.

The value of writing it out is knowing where it would fail. Allow steps in other directions and the correspondence breaks; allow the route to leave the grid and the letter-count condition is no longer sufficient; ask about routes on a grid with a hole and there is no formula at all, only an inclusion–exclusion over the forbidden corners.

Where the picture stops helping #

The grid must be rectangular and the steps must be two. Three directions give trinomial coefficients and a triangle in three dimensions, which is a real object with real identities and no drawing that fits on a page.

Large grids are not drawable. The figure with $126$ routes already declines to draw them, and the interesting coefficients are astronomically larger — $\binom{100}{50}$ is about $10^{29}$, and no picture of that many routes exists in any sense.

And a route argument proves an identity and not a formula. The route reading explains why $\binom{n}{k}$ satisfies the additive rule and why the identities hold; that $\binom{n}{k} = n!/(k!(n-k)!)$ is a different fact, proved by a different argument about orderings, and the two are often run together.

The distinction matters more than it sounds. Everything on this page would be equally true of any array satisfying the additive rule with ones down the edges, and the factorial formula is the extra fact that pins the array to a particular list of numbers. Change the edges to something else and the identities about routes survive unchanged while the formula does not — which is exactly what happens with obstacles, where the counts satisfy the same recurrence and no formula at all.

So the route picture is a picture of the recurrence rather than of the numbers, and that is why it keeps working when the numbers stop having a closed form. A reader who takes the grid as a way of remembering $n!/(k!(n-k)!)$ has taken the weaker half of it.

Two names and a long absence #

What a route costs to count #

The two ways of computing the same number differ in more than elegance, and the difference is the reason the grid picture is also a method.

Filling the grid by the additive rule costs one addition per corner — $(a+1)(b+1)$ of them for an $a$ by $b$ grid — and needs the whole grid, or at least one anti-diagonal at a time, in memory. Computing the single coefficient by the multiplicative rule costs about $b$ operations and needs nothing kept.

So for one unobstructed count the formula wins outright, and there is no reason to build a grid. The grid wins the moment anything about the problem is irregular: obstacles, a boundary the routes must respect, weights on the corners, steps of more than one kind. Every one of those breaks the formula and none of them breaks the recurrence, because the recurrence only ever asks about the two corners behind.

That is the general trade between a closed form and a recurrence, and it is worth stating in the direction that is usually left out. A closed form is faster and more fragile; a recurrence is slower and survives changes to the problem. A collection of problems that all admit closed forms is a collection somebody chose, and the recurrence is what remains when nobody chose.

Vandermonde published the identity in 1772. Zhu Shijie had it in 1303, in the Jade Mirror of the Four Unknowns, which also contains the triangle to nine rows; the Chinese name for the result reflects that and the European one does not.

The lattice-path reading is much more recent as a method. Counting routes on a grid is ancient as a puzzle, and using it systematically to prove binomial identities is largely twentieth-century — the phrase “combinatorial proof”, meaning a proof that exhibits a bijection rather than manipulating an expression, belongs to the same period.

That gap is worth noticing. The identities were known for six centuries before the standard way of explaining them was assembled, and during that time they were proved by algebra and remembered as a list. A technique that makes a body of results obvious can arrive centuries after the results, and its arrival is usually mistaken for a matter of taste rather than a change in what is understood.

The ladder from here #

Rungs above: how often a prime divides an entry, which is a question the route picture cannot see and the base-$p$ digits can. Catalan numbers, which count the routes that stay on one side of a diagonal and are the same object with one inequality added. The reflection principle in full, which counts constrained routes by turning them into unconstrained ones. The Lindström–Gessel–Viennot lemma, where several routes at once are counted by a determinant and the sign does the avoiding. And generating functions, where a whole row becomes a polynomial and Vandermonde’s convolution becomes an ordinary product.

Turning a count into a journey #

The move is worth naming because it is available far more often than it is used: when a number counts something, ask whether it counts something that happens in stages.

A subset does not obviously happen in stages. A route does — it is a sequence of steps — and once the object has a time in it, every identity becomes a statement about when something occurs. The stick identity is about when the last upward step happens; Vandermonde is about where the route is halfway; the reflection argument is about the first time a line is touched.

None of those questions can be asked of a subset, and all of them are natural for a route, which is why the same numbers are much easier to reason about in the second description. The subset and the route are the same object, and the difference between them is entirely in what the description makes it natural to ask.