Lattice path

Lattice path of length 5 in $\mathbb {Z} ^{2}$.

In combinatorics, "a lattice path $L$ in $\mathbb {Z} ^{d}$ of length $k$ with steps in $S$ is a sequence $v_{0},v_{1},\ldots ,v_{k}\in \mathbb {Z} ^{d}$ such that each consecutive difference $v_{i}-v_{i-1}$ lies in $S$." A lattice path may lie in any lattice in $\mathbb {R} ^{d}$ , but the integer lattice $\mathbb {Z} ^{d}$ is most commonly used.

An example of a lattice path in $\mathbb {Z} ^{2}$ of length 5 with steps in $S=\lbrace (2,0),(1,1),(0,-1)\rbrace$ is $L=\lbrace (-1,-2),(0,-1),(2,-1),(2,-2),(2,-3),(4,-3)\rbrace$.

North East lattice paths

A North East (NE) lattice path is a lattice path in $\mathbb {Z} ^{2}$ with steps in $S=\lbrace (0,1),(1,0)\rbrace$. The $(0,1)$ steps are called North steps and denoted by $N$'s; the $(1,0)$ steps are called East steps and denoted by $E$'s.

NE lattice paths most commonly begin at the origin. This convention allows us to encode all the information about a NE lattice path $L$ in a single permutation word. The length of the word gives us the number of steps of the lattice path, $k$. The order of the $N$'s and $E$'s communicates the sequence of $L$. Furthermore, the number of $N$'s and the number of $E$'s in the word determines the end point of $L$.

If the permutation word for a NE lattice path contains $n$ $N$steps and $e$ $E$ steps, and if the path begins at the origin, then the path necessarily ends at $(e,n)$. This follows because you have "walked" exactly $n$ steps North and $e$ steps East from $(0,0)$.

NE lattice paths starting from $(0,0)$ with exactly one $N$ and three $E$'s. The endpoint is necessarily at $(3,1)$.

Counting lattice paths

Lattice paths are often used to count other combinatorial objects. Similarly, there are many combinatorial objects that count the number of lattice paths of a certain kind. This occurs when the lattice paths are in bijection with the object in question. For example,

• Dyck paths are counted by the $n^{\text{th}}$ Catalan number $C_{n}$. A Dyck path is a lattice path in

$\mathbb {Z} ^{2}$ from $(0,0)$ to $(2n,0)$ with steps in $S=\lbrace (1,1),(1,-1)\rbrace$ that never passes below the $x$-axis. Equivalently, A Dyck path is a NE lattice path from $(0,0)$ to $(n,n)$ that "lies strictly below (but may touch) the diagonal $y=x$."

• The Schröder numbers count "the number of lattice paths from $(0,0)$ to $(n,n)$ with steps in $(1,0),(0,1)$ and $(1,1)$ that never rise above the line $y=x$".

• The number of NE lattice paths from $(0,0)$ to $(a,b)$ counts the counts the number of combinations of $a$ objects out of a set of $a+b$ objects.

Combinations and NE lattice paths

NE lattice paths have close connections to combinations, the binomial coefficient and Pascal's triangle. The diagram below demonstrates some of these connections.

The number of lattice paths from $(0,0)$ to $(2.3)$ is equal to ${\binom {2+3}{2}}={\binom {5}{2}}=10$.

The number of lattice paths from $(0,0)$ to $(n,k)$ is equal to the binomial coefficient, ${\binom {n}{k}}$. The diagram demonstrates this for $0\leq k\leq n=4$. If you rotate the diagram 135° clockwise about the origin and it it to include all $n,k\in \mathbb {N} \cup \lbrace 0\rbrace$, you obtain Pascal's triangle. This is a beautiful result, but no surprise because the $k^{\text{th}}$ entry of the $n^{\text{th}}$ row of Pascal's Triangle is the binomial coefficient ${\binom {n}{k}}$ .

Problems and proofs

The graphical representation of NE lattice paths lends itself beautifully to many bijective proofs involving combinations. Here are a few examples.

• Prove $\sum _{k=0}^{n}{\binom {n}{k}}^{2}={\binom {2n}{n}}$.

Proof:

Each NE lattice path passes through exactly one colored node.

Each NE lattice path passes through exactly one colored node.

Sets of NE lattice paths squared, with the second copy rotated 90$^{\circ }$ clockwise.

Sets of NE lattice paths squared, with the second copy rotated 90$^{\circ }$ clockwise.