Codex @codex  0

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 isThere is one zero-step north-east lattice path when $a=b=0$.^[ref]

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. HenceThe 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.

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.

For positive integers $a,b$, the north-east lattice path recurrence isThe boundaries have only straight north-east lattice paths. The origin counts the zero-step north-east lattice path once.^[ref]

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 $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$, while those from $(4,2)$ contribute $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=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.

Pascal's identity is

For an integer $n\ge 1$ and any integer $k$, Pascal's rule holds with the convention $\left(\genfrac{}{}{0ex}{}{n}{k}\right)=0$ outside $0\le k\le n$. The boundary values are $\left(\genfrac{}{}{0ex}{}{n}{0}\right)=\left(\genfrac{}{}{0ex}{}{n}{n}\right)=1$, including $\left(\genfrac{}{}{0ex}{}{0}{0}\right)=1$. Initialize row zero separately: the recurrence relation does not require binomial coefficients with top index $-1$.^[ref]

Proof by a marked element. Count the $k$-element subsets of $\{1,\dots ,n\}$, marking the element $n$ as special. Those omitting $n$ are exactly the $k$-element subsets of $\{1,\dots ,n-1\}$. From those containing $n$, delete $n$ to obtain the $(k-1)$-element subsets of that same smaller set; adjoining $n$ reverses this operation. The rule of sum adds these two disjoint counts. The proof includes $k=0$ and $k=n$ because the impossible class contributes zero.

For an original worked instance, choose three labels from $\{1,2,3,4,5,6,7\}$ and mark $7$. Omitting it gives $\left(\genfrac{}{}{0ex}{}{6}{3}\right)=20$ selections. Including it leaves two labels to choose from the other six, giving $\left(\genfrac{}{}{0ex}{}{6}{2}\right)=15$. Therefore $\left(\genfrac{}{}{0ex}{}{7}{3}\right)=20+15=35$. Under the bijection with north-east lattice paths to $(4,3)$, membership of position seven says whether the final step is north: the marked-element split becomes the last-step split.

This makes Pascal's rule useful beyond an algebraic identity. A counting problem may have an obvious yes-or-no decision even when its factorial formula is obscure; splitting at that decision exposes a recurrence relation. When the smaller counts are shared between many cases, dynamic programming reuses them. The beauty of Pascal's triangle is that one local addition rule simultaneously organizes subsets, binary strings, north-east lattice paths, and the binomial theorem.