= North-east lattice path recurrence
{title2=$P(a,b)=P(a-1,b)+P(a,b-1)$}
For <positive integers> $a,b$, the <north-east lattice path recurrence> is
$$
P(a,b)=P(a-1,b)+P(a,b-1),\qquad P(a,0)=P(0,b)=1.
$$
The boundaries have only straight <north-east lattice paths>. The origin counts the zero-step <north-east lattice path> once.<Discrete Mathematics: An Open Introduction (3rd edition) by Oscar Levin>[§1.2, Lattice Paths: split by the final horizontal or vertical step]{ref}
\b[Proof outline.] A <north-east lattice path> ending at $(a,b)$ has a final step either from $(a-1,b)$ or from $(a,b-1)$. Deleting that step gives a shorter <north-east lattice path>; appending it reverses the operation. The two classes are disjoint and exhaust all possibilities, so the <rule of sum> adds their counts. At $(4,3)$, the arrivals from $(3,3)$ contribute $\binom63=20$, while those from $(4,2)$ contribute $\binom62=15$: altogether $20+15=35$.
Set $P(a,b)=0$ if either <integer> coordinate is negative. Then the same <recurrence relation> applies on the nonnegative axes away from $(0,0)$: one predecessor contributes one, and the other contributes zero. Initialize $P(0,0)=1$ separately; applying the <recurrence relation> there would incorrectly give zero.
Computing the grid once in increasing order of $a+b$ is <dynamic programming>: every entry uses two earlier entries. If a specified <point> is forbidden, set its count to zero, then continue the same <recurrence relation> at allowed <points>. This counts <north-east lattice paths> avoiding the forbidden <points>, provided the origin and endpoint are allowed. The last-step argument remains valid because appending a step to an allowed endpoint cannot visit any new intermediate <integer lattice> <point>.
Back to article page
