Lattice path explained
In combinatorics, a lattice path in the -dimensional integer lattice of length with steps in the set, is a sequence of vectors such that each consecutive difference
lies in .
[1] A lattice path may lie in any
lattice in, but the integer lattice is most commonly used.
An example of a lattice path in 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
with steps in
S=\lbrace(0,1),(1,0)\rbrace
. The
steps are called North steps and denoted by
's;the
steps are called East steps and denoted by
's.
NE lattice paths most commonly begin at the origin. This convention allows us to encode all the information about a NE lattice path
in a single
permutation word. The length of the word gives us the number of steps of the lattice path,
. The order of the
's and
's communicates the sequence of
. Furthermore, the number of
's and the number of
's in the word determines the end point of
.
If the permutation word for a NE lattice path contains
steps and
steps, and if the path begins at the origin, then the path necessarily ends at
. This follows because you have "walked" exactly
steps North and
steps East from
.
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
Catalan number
. A
Dyck path is a lattice path in
from
to
with steps in
S=\lbrace(1,1),(1,-1)\rbrace
that never passes below the
-axis.
[2] Equivalently, a Dyck path is a NE lattice path from
to
that lies strictly below (but may touch) the diagonal
.
[3]
to
with steps in
and
that never rise above the diagonal
.
- The number of NE lattice paths from
to
counts the number of
combinations of
objects out of a set of
objects.
Combinations and NE lattice paths
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.
The number of lattice paths from
to
is equal to the
binomial coefficient
. The diagram shows this for
. If one rotates the diagram 135° clockwise about the origin and extend it to include all
n,k\inN\cup\lbrace0\rbrace
, one obtains Pascal's triangle. This result is no surprise, because the
entry of the
row of Pascal's Triangle is the binomial coefficient
.
Problems and proofs
The graphical representation of NE lattice paths lends itself to many bijective proofs involving combinations. Here are a few examples.
\binom{n}{k}2=\binom{2n}{n}
.
Proof: The right-hand side is equal to the number of NE lattice paths from
to
. Each of these NE lattice paths intersects exactly one of the lattice points in the rectangular array with coordinates
for
x\in\lbrace0,1,\ldots,n\rbrace
. This is shown in the figure below for
: Every NE lattice path from
to
intersects exactly one of the colored nodes.
On the left-hand side, the binomial coefficient squared,
, represents two copies of the set of NE lattice paths from
to
attached endpoint to start point. Rotate the second copy 90° clockwise. This does not change the combinatorics of the object:
\binom{n}{k}=\binom{n}{n-k}
. So the total number of lattice paths remains the same.
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
to
are accounted for. In particular, notice that any lattice path passing through the red lattice point (for example) is counted by the squared set of lattice paths (also shown in red).
See also
References
[4]
Notes and References
- Book: Stanley, Richard. Richard P. Stanley
. Richard P. Stanley. Enumerative Combinatorics, Volume 1. 2012. Cambridge University Press. 978-1-107-60262-5. 21. 2.
- Book: Stanley, Richard. Enumerative Combinatorics, Volume 2. 2001. Cambridge University Press. 978-0-521-78987-5. 173, 239.
- Web site: Wolfram MathWorld. 6 March 2014.
- Book: Song . Chunwei . Lattice Path Combinatorics and Special Counting Sequences: From an Enumerative Perspective . CRC Press . Boca Raton . 978-1032671758 . 1 .