= North-east lattice path
{title2=$E=(1,0),\quad N=(0,1)$}
A <north-east lattice path> is a <lattice path> whose allowed steps are $E=(1,0)$ and $N=(0,1)$. From $(0,0)$ to $(a,b)$, with <nonnegative integers> $a,b$, it has $a$ east steps and $b$ north steps. The number is
$$
\boxed{P(a,b)=\binom{a+b}{b}=\binom{a+b}{a}.}
$$
There is one zero-step <north-east lattice path> when $a=b=0$.<Discrete Mathematics: An Open Introduction (3rd edition) by Oscar Levin>[§1.2, Lattice Paths and Binomial Coefficients: encoding paths by step positions]{ref}
\b[Seven positions, thirty-five paths.] To reach $(4,3)$, choose the three positions occupied by north steps in a seven-symbol word. For example, the <subset> $\{2,4,7\}$ of $\{1,2,3,4,5,6,7\}$ gives `ENENEEN`: putting $N$ exactly in those positions and $E$ elsewhere reconstructs the <north-east lattice path>. Reading the north-step positions recovers the <subset>, so these two operations give a <bijection>. Hence
$$
P(4,3)=\binom73=\frac{7\cdot6\cdot5}{3\cdot2\cdot1}=35.
$$
The numerator counts ordered choices of three different positions; each <subset> occurs in $3!=6$ orders. Dividing by this <factorial> counts each <north-east lattice path> once. A <binary string> recording $N$ as $1$ and $E$ as $0$ gives the same example as `0101001`.
\Image[/north-east-path-positions-and-counts.png]
{title=A <bijection> from three chosen positions to a <north-east lattice path>, and the recursive grid giving $P(4,3)=35$}
{description=The original example `ENENEEN` reaches $(4,3)$. Both panels use east to the right and north upwards. The right panel counts all such <north-east lattice paths>, rather than just the displayed one: twenty arrive with a final east step and fifteen with a final north step.}
This interpretation is useful when arrangements have fixed totals but flexible order: a <subset>, a <binary string>, and a <north-east lattice path> become different views of one selection. It also separates endpoint restrictions from restrictions along the journey. Requiring the <lattice path> to avoid specified <points> changes the count; the unrestricted <binomial coefficient> no longer suffices, but the local <north-east lattice path recurrence> still suggests how to count allowed arrivals.
Back to article page
