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:

  1. It must start with an RR or LL step.
  2. If there are ever one more total RR steps than LL steps at some point in the path, the next step cannot be an LL step.  Similarly, if there are ever one more total LL steps than RR steps at some point in the path, the next step cannot be an RR step.

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.

For completeness, I guess I’ll add…

Theorem 5:  The number of NSEW n-step lattice paths achieving a maximum height of y is \displaystyle \binom{2n+1}{n+y+1}.

Proof: I proved this in my last post.

Advertisements
This entry was posted in combinatorics, lattice paths. Bookmark the permalink.

Leave a Reply

Fill in your details below or click an icon to log in:

WordPress.com Logo

You are commenting using your WordPress.com account. Log Out / Change )

Twitter picture

You are commenting using your Twitter account. Log Out / Change )

Facebook photo

You are commenting using your Facebook account. Log Out / Change )

Google+ photo

You are commenting using your Google+ account. Log Out / Change )

Connecting to %s