Positive and recurrent walks

It is rather well-known that the number of up-down walks that start at $0$ and stay nonnegative until ending at $0$ after $2n$ steps is the $n$th Catalan number, $C_n=\frac{1}{n+1}\binom{2n}{n}$. Such paths, in which we either go up by $1$ or down by $1$ at each step and never fall below the $x$-axis, are called Dyck paths. An example for $n=5$ is shown below.

walk1

What is not so well-known is that:

The number of up-down walks of length $2n$ that stay nonnegative, but do not necessarily return to $0$ at the end, is simply $\binom{2n}{n}$.

walk2

This fact came up in my research a few days ago, and I figured that this had to be a trivial theorem that was easy to prove. Several hours of failed attempts later, I found myself googling “positive walks central binomial coefficients” and came across a wonderful recent paper of M. van Leeuwen.

He describes a bijective way of proving this fact by matching the walks with the recurrent (returning-to-zero) walks that are not necessarily positive. Clearly there are $\binom{2n}{n}$ such walks of the latter sort, since they can be thought of as walks from one corner to the opposite corner on a rotated $n\times n$ grid.

walk3

To construct the bijection, consider any recurrent walk from $0$ to $2n$. If the walk is already positive, simply map it to itself. If the walk becomes negative at any point, consider the first times the walk reaches $-1,-2,\ldots,-d$, where $-d$ is the minimum value of the walk. The step just before each of these positions must have been a down-step, and by simply changing each of these $d$ down-steps to an up-step, we end up with a positive walk of length $2n$.

walk4

To see that this is bijective, notice that if we had flipped $d$ of the down-steps of the recurrent walk, the last step of the new walk ends at height $2d$. So, to reverse the process, let $2d$ be the ending height of a given positive walk, and we wish to flip $d$ of the up-steps back to down-steps. But the ones we had flipped must be the steps following the last visits to heights $0,1,2,\ldots,d-1$ in the positive walk, by the above construction, so we simply find these visits and flip down the steps following each of them. Beautiful!

3 thoughts on “Positive and recurrent walks

  1. Hi Maria,

    Very nice! This reminds me very much of the following problem: given a positive integer n, construct a bijection from the n-subsets of [2n+1] to the (n+1)-subsets of [2n+1] such that every n-subset is contained in its image.

    Steven

  2. I’ve seen this bijection rediscovered and reproven so many times now that I start to wonder where it appeared first. The earliest mention I know is in Christian Stump’s 2008 PhD thesis, Proposition 2.33., but clearly it must have been around way longer.

    • Interesting, glad to hear the alternate reference. I think it’s often re-proven because you usually don’t see it mentioned in the standard combinatorics texts. Hopefully a combinatorics text will come out that includes it, so that we can have a standard reference for it.

Leave a Reply to Steven Karp Cancel reply

Your email address will not be published. Required fields are marked *