Lattice path

A North-East (NE) lattice path is a lattice path in $\backslash mathbb\{Z\}^2$ with steps in $S\; =\; \backslash lbrace\; (0,1),\; (1,0)\; \backslash 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 encoding all the information about a NE lattice path $L$ in a single permutation word. The length of the word gives 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 the path "walks" exactly $n$ steps North and $e$ steps East from $(0,0)$.

File:1N3E SVG.svg

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^\{\backslash text\{th\}\}$ Catalan number $C\_n$. A Dyck path is a lattice path in $\backslash mathbb\{Z\}^2$ from $(0,0)$ to $(2n,0)$ with steps in $S\; =\; \backslash lbrace\; (1,1),\; (1,-1)\; \backslash rbrace$ that never passes below the $x$-axis.{{cite book|authorlink=Richard P. Stanley|last=Stanley|first=Richard|title=Enumerative Combinatorics, Volume 2|date=2001|publisher=Cambridge University Press|isbn=978-0-521-78987-5|pages=173, 239}} 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$.{{cite web|title=Wolfram MathWorld|url=http://mathworld.wolfram.com/DyckPath.html|accessdate=6 March 2014}}
• 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 diagonal $y=x$.
• The number of NE lattice paths from $(0,0)$ to $(a,b)$ counts the number of combinations of $a$ objects out of a set of $a\; +\; b$ objects.

NE lattice paths have close connections to the number of combinations, which are counted by the binomial coefficient, and arranged in Pascal's triangle. The diagram below demonstrates some of these connections.

File:Walking on Pascal's Triangle SVG.svg

The number of lattice paths from $(0,0)$ to $(n,k)$ is equal to the binomial coefficient $\backslash binom\{n+k\}\{n\}$. The diagram shows this for $0\; \backslash leq\; k\; \backslash leq\; n\; =4$. If one rotates the diagram 135° clockwise about the origin and extends it to include all $n,k\; \backslash in\; \backslash mathbb\{N\}\; \backslash cup\; \backslash lbrace\; 0\; \backslash rbrace$, then one obtains Pascal's triangle. This result is because the $k^\{\backslash text\{th\}\}$ entry of the $n^\{\backslash text\{th\}\}$ row of Pascal's Triangle is the binomial coefficient $\backslash binom\{n\}\{k\}$.

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

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

Proof: The right-hand side is equal to the number of NE lattice paths from $(0,0)$ to $(n,n)$. Each of these NE lattice paths intersects exactly one of the lattice points in the rectangular array with coordinates $(x,\; n-x)$ for $x\; \backslash in\; \backslash lbrace\; 0,\; 1,\; \backslash ldots,\; n\; \backslash rbrace$. This is shown in the figure below for $n=4$: Every NE lattice path from $(0,0)$ to $(4,4)$ intersects exactly one of the colored nodes.

Image:NE nodes SVG.svg

On the left-hand side, the binomial coefficient squared, $\backslash binom\{n\}\{k\}^2$, represents two copies of the set of NE lattice paths from $(0,0)$ to $(k,n-k)$ attached endpoint-to-startpoint. Rotating the second copy 90° clockwise does not change the combinatorics of the object: $\backslash binom\{n\}\{k\}\; =\; \backslash binom\{n\}\{n-k\}$. So the total number of lattice paths remains the same.

Image:Squared.png

Superimpose the NE lattice paths squared onto the same rectangular array, as seen in the figure below. We see that all NE lattice paths from $(0,0)$ to $(n,n)$ are accounted for. In particular, any lattice path passing through the red lattice point (for example) is counted by the squared set of lattice paths (also shown in red). $\backslash Box$

File:Superimposed lattice paths squared.jpg

• Tadepalli Venkata Narayana

{{Reflist}}

• {{cite book|authorlink=Tadepalli Venkata Narayana|last=Narayana|first=Tadepalli Venkata|title=Lattice Path Combinatorics with Statistical Applications |date=15 December 1979 |publisher=University of Toronto Press |location=Toronto |isbn=978-1487587284 |edition=1 |url=https://utorontopress.com/9781487582586/lattice-path-combinatorics-with-statistical-applications-mathematical-expositions-23}}
• {{cite book|authorlink=Chunwei Song|last=Song|first=Chunwei|title=Lattice Path Combinatorics and Special Counting Sequences: From an Enumerative Perspective |date=2024 |publisher=CRC Press |location=Boca Raton |isbn=978-1032671758 |edition=1 |doi=10.1201/9781003509912 |url=https://www.taylorfrancis.com/books/mono/10.1201/9781003509912/lattice-path-combinatorics-special-counting-sequences-chunwei-song}}

Category:Enumerative combinatorics