Article
Full entry |
PDF
(0.2 MB)
Feedback
PDF
(0.2 MB)
Feedback
Keywords:
lattice path; enumeration; shortest path; generating function
lattice path; enumeration; shortest path; generating function
Summary:
Let $S$ be a finite set of integer vectors. We consider lattice paths that use only the vectors in $S$. We focus on paths that use a fixed number of vectors. We generally assume vectors in $S$ have a fixed coordinate sum, which allows us to determine the number of vectors in a path, which we call its length. We count the number of paths with fixed length for various sets of vectors $S$. We then use our enumeration results to determine the minimal length path given a terminal point. First, we explore this problem in $S \subseteq \mathbb {N}^3$. After solving the problem of enumeration and determining the minimal length for various sets $S\subseteq \mathbb {N}^3$, we solve these problems for a general case $S=\{(1,0),(0,1),(u,v),(v,u)\}$. We conclude with an enumeration problem of paths that stay weakly below the line $y=x$.
References:
[1] Evoniuk, J., Klee, S., Magnan, V.: Enumerating minimal length lattice paths. J. Integer Seq. 21 (2018), Article ID 18.3.6, 12 pages. MR 3805751 | Zbl 1384.05020
[2] Firoozi, F.: Enumeration of Lattice Paths with Respect to a Linear Boundary. Simon Fraser University, Burnaby (2023), Available at https://summit.sfu.ca/item/36159\kern0pt
[3] Humphreys, K.: A history and a survey of lattice path enumeration. J. Stat. Plann. Inference 140 (2010), 2237-2254. DOI 10.1016/j.jspi.2010.01.020 | MR 2609483 | Zbl 1204.05015
[4] Iwanojko, N., Klee, S., Lasher, B., Volpi, E.: Enumerating lattice walks with prescribed steps. J. Integer Seq. 23 (2020), Article ID 20.4.3, 15 pages. MR 4105870 | Zbl 1439.05017
[5] Krattenthaler, C.: Lattice path enumeration. Handbook of Enumerative Combinatorics Discrete Mathematics and its Applications. CRC Press, Boca Raton (2015), 589-678. DOI 10.1201/b18255-16 | MR 3409351 | Zbl 1332.05009
[6] Sloane, N. J. A.: The On-Line Encyclopedia of Integer Sequences. Available at\ https://oeis.org/ Zbl 1159.11327
[7] White, V.: Enumeration of Lattice Paths with Restrictions. Georgia Southern University, Statesboro (2024), Available at\ https://digitalcommons.georgiasouthern.edu/etd/2799/\kern0pt
Search
Partner of
