## NSEW Lattice Path Statistics

My last post gave a derivation for the number of NSEW lattice paths starting at the origin that achieve a maximum height of $y$.  I’ve been playing around with more NSEW lattice path statistics lately, and I thought I would record some of my observations (probably for my own future reference more than anything else).  All lattice paths start at the origin.

Theorem 1: The number of $n$-step NSEW lattice paths ending at $(x,y)$ is $\displaystyle \binom{n}{(n+x+y)/2} \binom{n}{(n-x+y)/2}.$

Proof: I proved this in my last post.

Theorem 2: The number of $n$-step NSEW lattice paths ending at a height of $y$ is $\displaystyle \binom{2n}{n+y}.$

Proof: I also proved this in my last post.

Theorem 3: The number of $n$-step NSEW lattice paths ending on the line $y = x+k$ is $\displaystyle 2^n \binom{n}{(n+k)/2}.$

Proof 1: By Theorem 1, this is $\displaystyle \sum_x \binom{n}{(n+k)/2+x} \binom{n}{(n+k)/2} = 2^n \binom{n}{(n+k)/2}.$

Proof 2: In order for a path to end on the line $y = x+k$, there must be $k$ more north and west steps than there are south and east steps.  (This is because each north or west step moves you from some line $y = x + b$ to $y = x + b + 1$, and each south or east step moves you in the other direction.)  There are $\binom{n}{(n+k)/2}$ ways to choose which of the $n$ steps will be north or west steps; the others will be south or east steps.  Once that decision is made, there are two choices (north or west, south or east) for each of the $n$ steps.

Theorem 4: The number of $n$-step NSEW lattice paths that avoid the line $y = 0$ after the first step is $\binom{2n}{n}$.

Proof: This proof is by a bijection to $2n$-step one-dimensional lattice paths that never return to the start after the first step; it is known that there are $\binom{2n}{n}$ of these.  Given a $2n$-step 1D lattice path that can take a right or left move at each step, each pair of steps in the path must be of the form RR, RL, LR, or LL.  A 1D lattice path that never returns to the origin can thus be characterized in the following fashion:

Now, associate N $\leftrightarrow$ RR, E $\leftrightarrow$ RL, W $\leftrightarrow$ LR, S $\leftrightarrow$ LL.  Then the above characterization for 1D lattice paths that never return to the origin also characterizes NSEW lattice paths that never return to the line $y= 0$.  Thus the number of such paths must be the same in each case.
Theorem 5:  The number of NSEW $n$-step lattice paths achieving a maximum height of $y$ is $\displaystyle \binom{2n+1}{n+y+1}.$