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.

Row $n$ of Pascal's triangle consists of the binomial coefficients $\left(\genfrac{}{}{0ex}{}{n}{0}\right),\dots ,\left(\genfrac{}{}{0ex}{}{n}{n}\right)$, beginning with row $0$. Boundary entries are one, and Pascal's identity says each interior entry is the sum of the two entries above it. The hockey-stick identity evaluates sums along its diagonals.

The highlighted entry in the binomial coefficient illustration is $\left(\genfrac{}{}{0ex}{}{5}{2}\right)=10$. Split two-person teams according to whether they contain the fifth person: six choose both members from the other four, and four contain the fifth person together with one of those four. Thus $10=6+4$. All entries can be generated by the same local rule, so a large table of counts needs no repeated enumeration of its subsets.

Reading row seven. Label the entries in each row from $k=0$ on the left through $k=n$ on the right. Rows zero through seven are shown below. The highlighted entry $T_{7,3}=35$ comes from $T_{6,2}=15$ and $T_{6,3}=20$. Starting with row zero $(1)$, the edges remain one and Pascal's rule determines every interior entry, so mathematical induction uniquely determines the whole array.

The triangular and rectangular layouts describe the same entries. For a north-east lattice path ending at $(a,b)$, set $n=a+b$ and $k=b$, so $P(a,b)=T_{n,k}$. The predecessor $(a-1,b)$ has indices $(n-1,k)$, while $(a,b-1)$ has indices $(n-1,k-1)$. Thus the grid's west and south arrivals are exactly the triangle's two parents. This change of indices explains why the north-east lattice path recurrence and Pascal's rule agree.

There is also a global check on the local construction: row $n$ sums to $2^n$. Every subset of an $n$-element set appears exactly once among the classes of sizes $0,\dots ,n$, and each element has two inclusion choices by the rule of product. In row seven, $1+7+21+35+35+21+7+1=128=2^7$. Replacing every subset by its complement reverses the row, explaining $T_{n,k}=T_{n,n-k}$. The binomial theorem packages the whole row as the coefficients of $(1+x{)}^n$.

Blaise Pascal's Traité du triangle arithmétique, published in 1665, presents an arithmetic array and connects it to combinations, games of chance, and powers of binomial expressions. This makes the connection between a counting table and several applications visible in the original work. ^[ref] The University of Cambridge's account of the treatise explains its 1654 composition and the organization of these applications. ^[ref]