Counting the paths that go wrong

Here is a counting problem with a clean statement and no obvious answer. A path goes from one corner of a square grid to the opposite corner, moving only up and right. Count the paths that never dip below the diagonal.

Counting all the paths is immediate: a path across an $n$ by $n$ grid is a sequence of $n$ ups and $n$ rights in some order, so there are $\binom{2n}{n}$ of them. The constraint is what makes it hard. There is no way to build a good path step by step while keeping the count, because whether a step is allowed depends on everything that came before it.

The trick is to give up on counting the good ones and count the bad ones instead. That sounds like a worse problem — the bad paths are defined by the same awkward condition, negated — and it is a strictly easier one, because a bad path has a feature to grab hold of.

The feature, and what to do with it #

A bad path is one that at some moment has taken more rights than ups. Follow it from the start and there is a first such moment — the first step after which the count of rights exceeds the count of ups by exactly one. In grid terms, the first time the path touches the line one below the diagonal.

That first moment is canonical. It does not depend on any choice, it exists for every bad path and for no good one, and it splits the path into a head and a tail.

Now reflect the tail: exchange every up-step for a right-step and every right-step for an up-step, from that moment to the end. Geometrically this is the mirror image in the line the path has just touched.

Follow what the reflection does to the endpoint. Say the head has $a$ ups and $a+1$ rights — that is what touching the line one below the diagonal means. The tail then has $n - a$ ups and $n - a - 1$ rights, and reflecting swaps them. So the reflected path has $(a+1) + (n-a) = n+1$ rights and $a + (n - a - 1) = n - 1$ ups, and it ends at $(n+1, n-1)$ instead of $(n, n)$.

Every bad path becomes a path to a corner one step away, and the arithmetic that says so does not depend on where the first bad step was.

Why it is a bijection and not merely a map #

The count is only useful if the correspondence is exact in both directions, and the argument for that is the same observation used backwards.

Take any path from the origin to $(n+1, n-1)$. It ends with more rights than ups, so at some point it crossed the line one below the diagonal, and it has a first such crossing. Reflect everything after that crossing. The result is a path with $n$ of each, and it touches the line, so it is bad. And reflecting twice returns the original, because the first crossing is unchanged by reflecting after it.

So the two operations are inverse to each other, and

$$\#\{\text{bad paths}\} = \binom{2n}{n+1}.$$

The good paths are what is left:

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

That difference simplifies, and the simplification is worth doing rather than quoting. Write both coefficients out:

$$\binom{2n}{n} = \frac{(2n)!}{n!\,n!}, \qquad \binom{2n}{n+1} = \frac{(2n)!}{(n+1)!\,(n-1)!}.$$

Take the first out as a factor. The second is the first multiplied by $\frac{n!\,n!}{(n+1)!\,(n-1)!} = \frac{n}{n+1}$, so the difference is $\binom{2n}{n}\left(1 - \frac{n}{n+1}\right)$, and the bracket is $\frac{1}{n+1}$. Hence

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

which is the closed form the anchor’s first essay quoted and did not derive.

The division by $n+1$ is a clue, and it is a clue about something else #

A closed form containing a division is worth being suspicious of. $\binom{2n}{n}$ is a count of things; dividing it by $n+1$ says that the good paths are the orbits of some $(n+1)$-fold symmetry acting on all the paths, and a symmetry is a much better explanation than a cancellation of factorials.

There is one, and it is the cycle lemma of Dvoretzky and Motzkin. Take a sequence of $n$ ups and $n+1$ rights — one extra right — and consider its $2n+1$ cyclic rotations. Exactly one of them has the property that every proper prefix has more ups than rights. So the sequences of that kind number $\binom{2n+1}{n}/(2n+1)$, and a short manipulation turns that into the Catalan number.

The reflection argument and the cycle lemma prove the same formula and explain different things. Reflection explains the subtraction: two binomial coefficients, one for everything and one for the failures. The cycle lemma explains the division: one representative per rotation class. A formula with both a subtraction and a division has two proofs because it is two facts.

The cycle lemma, worked #

The cycle lemma deserves to be carried out once rather than cited, because its proof is three lines and it is the cleanest argument on this rung.

Take any arrangement of $n$ ups and $n+1$ rights. Read it as a walk that goes $+1$ for an up and $-1$ for a right; it ends at $-1$. Now consider the $2n+1$ cyclic rotations of the arrangement, and for each ask whether every proper prefix is strictly positive.

Exactly one rotation has that property. To see it, plot the running total of the whole arrangement and find the position at which the running total first attains its overall minimum. Rotating so that the arrangement begins immediately after that position makes every subsequent partial sum strictly greater than zero, because the minimum has been placed at the end; and no other rotation can work, because any other starting point leaves some earlier prefix reaching down to the minimum.

Since each rotation class has $2n+1$ members and contributes exactly one good arrangement, the good arrangements number

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

and expanding that gives $\frac{1}{n+1}\binom{2n}{n}$ again.

Two things about the argument are worth noticing. It never mentions the constraint’s difficulty — the awkward “at every moment” condition is handled by choosing where to start, not by tracking anything. And the number $2n+1$ being odd is quietly load-bearing: the rotations of a sequence of length $2n+1$ are all distinct unless the sequence is periodic, and a sequence of length $2n+1$ with an odd number of symbols of one kind cannot be periodic with a smaller period. Run the same argument on an even-length sequence and the rotation classes have different sizes, and the division fails.

That is the whole reason the extra right-step is added. Nobody wants to count arrangements of $n$ ups and $n+1$ rights; the extra step is there to make the length odd so the rotation classes are uniform, and the answer is then translated back. A proof that needs an artificial extra element in order to make a symmetry act freely is a common and underrated shape.

The same problem, wearing a rosette #

The constraint never more rights than ups is the same as never behind in the count, and that is a question about an election.

Two candidates receive $p$ and $q$ votes with $p > q$, and the ballots are counted one at a time in a random order. What is the probability that the eventual winner is ahead at every moment of the count? The answer is $(p-q)/(p+q)$, which is Bertrand’s ballot problem of 1887, and the standard proof is the reflection above with the grid relabelled: a count is a path, being ahead is staying above the diagonal, and the bad counts are matched to counts of a different election.

The equal case $p = q$ is the Catalan situation, and the ballot formula degenerates to zero — which is correct, since a tied election is behind at the end. What the Catalan count asks instead is that the winner never trail, allowing ties, which shifts the diagonal by half a step and is the version the grid draws.

And it is a random walk that never goes negative #

Replace up by $+1$ and right by $-1$ and a path becomes a walk on the integers that starts and ends at zero. Staying above the diagonal becomes staying non-negative.

So the Catalan number counts the walks of length $2n$ from zero to zero that never go below zero, and the reflection argument is the reflection principle of random walk theory, where it is used to compute the distribution of the maximum. The identity there is stated as: the number of walks from $a$ to $b$ touching a level $L$ equals the number of walks from $a$ to the reflection of $b$ in $L$. That is the same sentence as the one above, with the level named rather than fixed at one below the diagonal.

It is worth being careful about one detail, because it is where the two formulations differ by a half-step. A walk of length $2n$ from zero to zero that never goes negative is allowed to touch zero, and touching zero is exactly the path touching the diagonal. A walk required to stay strictly positive after its first step is a different count, and it comes out as $C_{n-1}$ rather than $C_n$. The two conventions differ by one index, they are both standard, and almost every disagreement about a Catalan identity in the literature is one of them.

This is the reason the sequence is inescapable in probability. A queue that never empties into debt, a stack that never pops from empty, a bracket sequence that never closes what was not opened — every one is a non-negative walk, and every one is counted by the same numbers. The counting problem was never really about grids.

Running the same check at a size where nothing can be verified by inspection is the point of that figure rather than a bigger version of the last one. A bijection is exactly the kind of claim that holds on every small case anybody draws and fails on the first case nobody does, and the only defence is to make the machine check the whole of a case too large to look at.

What the reflection cannot count #

The method is sharper than it looks and also narrower, and the boundary is worth locating exactly.

It works because the reflection is an involution on paths, which needs the step set to be symmetric under the reflection. Ups and rights exchange cleanly. Add a third kind of step — a diagonal step, say, which is its own mirror image — and the argument still works, giving the Motzkin numbers. Make the steps asymmetric, so that up-steps are of size one and down-steps of size two, and the reflection has nothing to exchange them for: the resulting sequences are counted by no such simple difference, and the honest tools are generating functions.

There is a third boundary, and it is the one that matters most in practice: two barriers instead of one. Counting paths that stay between two lines cannot be done by a single reflection, because reflecting off one barrier can push the path through the other. What replaces it is an infinite alternating sum over the words in the group generated by the two reflections — reflect off the upper, then the lower, then the upper again — and the terms cancel in pairs until the path is too short to reach the barriers at all. The result is a finite but genuinely alternating sum rather than a difference of two terms, and it is the method of images, arriving in combinatorics from the same place it arrives in the theory of heat.

The same failure appears in a subtler form when the barrier is not straight. Counting paths that stay above a line of slope other than one, or above a curve, is a genuinely harder problem, and the cases with clean answers are exactly the ones where a reflection or a rotation happens to be available. The general theory — the kernel method, and Lindström–Gessel–Viennot for several non-crossing paths at once — exists precisely because reflection runs out.

Where the argument came from #

The reflection is usually attributed to Désiré André, who used it in 1887 on Bertrand’s ballot problem in the same volume in which Bertrand had posed it. That attribution is not quite right, and the correction is interesting.

André’s actual argument does not reflect anything. It sets up a correspondence between the bad sequences beginning with a vote for one candidate and those beginning with a vote for the other, and derives the answer from that pairing. The reflection argument as it is now taught — find the first crossing, mirror the tail — appears later, in Aebly and Mirimanoff around 1923, and became standard because it is easier to see and generalises to random walks.

So the name records who solved the problem rather than who found the argument, which is the ordinary way names attach. What makes the case worth noting is that the two proofs are genuinely different: André’s pairing is between two sets of bad sequences and gives the answer by a symmetry, while the reflection is between bad sequences and a different corner’s paths and gives it by a complement. The second is the one that turned out to have a hundred years of consequences, and it was found by people looking for a clearer exposition of the first.

How much the constraint costs #

Comparing the two counts says something the formula obscures. There are $\binom{2n}{n}$ paths and $C_n$ good ones, so the fraction of paths that stay above the diagonal is $1/(n+1)$.

That is a striking answer for two reasons. It is exactly a reciprocal, with no approximation and no error term, for every $n$ — which is again the cycle lemma talking. And it decays slowly: at $n = 100$ about one path in a hundred and one is good, which is small but nothing like the exponential rarity one might guess from a constraint that has to hold at every one of two hundred steps.

The reason the decay is only polynomial is the reason the whole subject is interesting. A random walk of length $2n$ returning to zero stays non-negative with probability of order $1/n$ because the constraint is nearly free most of the time — a walk that has wandered far from zero is in no danger, and all the difficulty is concentrated near the origin. Constraints that bind everywhere cost exponentially; constraints that bind on a boundary cost polynomially, and this one binds on a boundary. That is the same distinction an inclusion–exclusion count runs into from the other side.

What the pictures cannot show #

The grids drawn are three and four on a side and the argument is about all sizes. The reflection is checked exhaustively at the sizes drawn, which means every bad path on a grid of that size, and that is a complete verification of a small case rather than evidence for a general one. The general statement is the paragraph about the head and the tail, and it is prose.

The first bad step is marked and the reflection line is dashed, and neither is part of the path. They are features of the analysis, not of the object, and a reader could be forgiven for thinking a path knows where its first bad step is. It does not; the observer finds it.

And the bijection is drawn as two pictures side by side, which shows one instance of a correspondence whose content is that it works for all of them and misses nothing. A picture of a bijection is always a picture of one pair; what makes it a bijection is the argument that the inverse exists, and there is nothing to draw of that.

Where the ladder goes next #

The next rung takes the correspondence seriously rather than instrumentally: one word read as four different objects, where the path, the bracket string, the triangulated polygon and the binary tree are shown to be one thing in four notations. After that the sequence is given an equation of its own, and finally the triangulations are assembled into a solid whose corners they are.

Sideways, the subtraction here is the two-term case of inclusion and exclusion, the binomial coefficients are read off Pascal’s triangle, and the walk formulation is the recurrent walk on a line conditioned to return.

What is worth carrying away #

When a set is hard to count, count its complement inside something easy, and look for the canonical feature that every element of the complement has.

The good paths have no feature: they are defined by an absence. The bad ones all have a first bad step, and a feature that exists exactly once per object is a hook a bijection can hang on. Everything else here is bookkeeping.

The habit worth taking is to read a formula’s shape as a claim about a proof. A subtraction of two counts says complement; a division by $n+1$ says symmetry with $n+1$ elements. This formula has both, so it has two proofs, and each explains the half of the formula the other does not.