## The Number of NSEW Lattice Paths with a Maximum Height of y

I’ve been thinking and learning some about lattice path statistics lately, and a couple of days ago I worked out the answer to the following question (with help from some suggestions from Anthony Quas via Math Overflow).

Suppose we have a lattice path in 2D starting at the origin, in which north, south, east, and west steps are allowed.  How many lattice paths with $n$ steps have a maximum height of $y$?  (By “maximum height” I mean the highest vertical distance the path achieves over the course of its entire length.)

To answer this question we need a couple of other lattice path statistics.

First, let’s count how many lattice paths with $n$ steps end up at a particular point $(x,y)$.  Let $(X_n,Y_n)$ denote the final position of an $n$-step NSEW lattice path.  We want $N((X_n,Y_n) = (x,y))$.  A nice way to count these involves making the transformation $(x,y) \to (x+y,y-x)$ and considering NW, NE, SW, and SE steps instead.  Since these four diagonal steps are of the form $(\pm 1, \pm 1)$, we need to count the number of ways to choose $n$ total +1s and -1s to get to $x+y$ for the first coordinate, and then multiply that by the number of ways to choose $n$ total +1s and -1s to get to $y-x$.  (In other words, the transformation allows us to deal with the two coordinates separately.)  If we let $p$ and $q$ denote the number of +1s and -1s needed to reach $x+y$, we have $p + q = n$ and $p - q = x+y$.  Thus $p = (n + x + y)/2$, and so the number of ways to obtain the first coordinate is $\binom{n}{(n+x+y)/2}$.  Similarly the number of ways to obtain the second coordinate is $\binom{n}{(n+y-x)/2}$, and so we get $\displaystyle N((X_n,Y_n) = (x,y)) = \binom{n}{(n+x+y)/2}\binom{n}{(n+y-x)/2}.$

Next, let’s find the number $N(Y_n = y)$ of $n$-step NSEW lattice paths whose final position has a height of $y$.  To get this, we sum the answer we just obtained over all values of $x$.  The  Chu-Vandermonde identity comes in handy, and we have $\displaystyle N(Y_n = y) = \sum_x \binom{n}{(n+x+y)/2}\binom{n}{(n+y-x)/2} = \binom{2n}{n+y}$.

Now we’re ready to find the number of $n$-step NSEW lattice paths that have a maximum height of $y$.  For a particular $n$-step path, let $M_n$ denote its maximum height.  We want $N(M_n = y)$.  To get this, let’s first look at the number of paths that end at a height of $b$ and have a maximum height of $y$ or greater.  If $b \geq y$, then $N(M_n \geq y, Y_n = b) = N(Y_n = b)$.

Then consider the case $b < y$.   For any path that ends at $b$ and reaches a height of at least $y,$ take the part of that path after the first step that reaches $y$ and reflect it across the horizontal line at height $y$.  Any path that ends at a height of $b$ gets transformed into one that ends at a height of $2y-b$.  This transformation is reversible, and so if $b < y$ then  $N(M_n \geq y, Y_n = b) = N(Y_n = 2y-b)$.  (This trick is called the reflection principle and is a common technique for working with lattice paths.)

Putting this together, we get that

$\displaystyle N(M_n \geq y) = \sum_{b \geq y} N(Y_n = b) + \sum_{b \leq y-1} N(Y_n = 2y-b)$
$\displaystyle = \sum_{b \geq y} N(Y_n = b) + \sum_{b \geq y+1} N(Y_n = b).$

Thus $\displaystyle N(M_n = y) = N(M_n \geq y) - N(M_n \geq y+1) = N(Y_n = y) + N(Y_n = y+1),$
which gives us the really nice answer $\displaystyle N(M_n = y) = \binom{2n}{n+y} + \binom{2n}{n+y+1} = \binom{2n+1}{n+y+1}.$