Abstract
The enumeration of lattice paths is an important counting model in enumerative combinatorics. Because it can provide powerful methods and technical support in the study of discrete structural objects in different disciplines, it has attracted much attention and is a hot research field. In this paper, we summarize two kinds of the lattice path counting models that are single lattice paths and family of nonintersecting lattice paths and their applications in terms of the change of dimensions, steps, constrained conditions, the positions of starting and end points, and so on. (1) The progress of classical lattice path such as Dyck lattice is introduced. (2) A method to study the enumeration of lattice paths problem by generating function is introduced. (3) Some methods of studying the enumeration of lattice paths problem by matrix are introduced. (4) The family of lattice paths problem and some counting methods are introduced. (5) Some applications of family of lattice paths in symmetric function theory are introduced, and a related open problem is proposed.
Article PDF
Similar content being viewed by others
Avoid common mistakes on your manuscript.
References
Banderier C, Flajolet P. Basic analytic combinatorics of directed lattice paths. Theoret Comput Sci, 2002, 281(1/2): 37–80
Banderier C, Krattenthaler C, Krinik A, et al. Explicit formulas for enumeration of lattice paths: basketball and the kernel method. In: Lattice Path Combinatorics and Applications. Dev Math, Vol 58. Cham: Springer, 2019, 78–118
Banderier C, Schwer S. Why Delannoy numbers? J Statist Plann Inference, 2005, 135(1): 40–54
Banderier C, Wallner M. Local time for lattice paths and the associated limit laws. arXiv: 1805.09065
Bell J P, Chen S S. Power series with coefficients from a finite set. J Combin Theory Ser A, 2017, 151: 241–253
Benjamin A T, Cameron N T. Counting on determinants. Amer Math Monthly, 2005, 112(6): 481–492
Bostan A, Bousquet-Mélou M, Kauers M, et al. On 3-dimensional lattice walks confined to the positive octant. Ann Comb, 2016, 20(4): 661–704
Bostan A, Chyzak F, van Hoeij M, et al. Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. European J Combin, 2017, 61: 242–275
Bostan A, Chyzak F, van Hoeij M, et al. Explicit formula for the generating series of diagonal 3D rook paths. Sém Lothar Combin, 2011/2012, 66: Art B66a (27 pp)
Bostan A, Kauers M. Automatic classification of restricted lattice walks. In: 21st International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2009), DMTCS Proc, Vol AK. Nancy: Assoc Discrete Math Theor Comput Sci, 2009, 201–215
Bousquet-Mélou M. An elementary solution of Gessel’s walks in the quadrant. Adv Math, 2016, 303: 1171–1189
Bousquet-Mélou M, Mishna M. Walks with small steps in the quarter plane. In: Algorithmic Probability and Combinatorics. Contemp Math, Vol 520. Providence: AMS, 2010, 1–39
Bousquet-Mélou M, Petkovšek M. Linear recurrences with constant coefficients: the multivariate case. Discrete Math, 2000, 225(1/2/3): 51–75
Bousquet-Mélou M, Petkovšek M. Walks confined in a quadrant are not always D-finite. Theoretical Computer Science, 2003, 307(2): 257–276
Brak R, Essam J, Osborn J, et al. Lattice paths and the constant term. J Phys Conf Ser, 2006, 42(1): 47–58
Carrozza S, Tanasa A. Pfaffians and nonintersecting paths in graphs with cycles: Grassmann algebra methods. Adv in Appl Math, 2018, 93: 108–120
Chalykh O A. Macdonald polynomials and algebraic integrability. Adv Math, 2002, 166(2): 193–259
Chen S S, Chyzak F, Feng R Y, et al. On the existence of telescopers for mixed hypergeometric terms. J Symbolic Comput. 2015, 68: Part 1, 1–26
Chen W Y C, Deng E Y P, Du R R X. Reduction of m-regular noncrossing partitions. European J Combin, 2005, 26(2): 237–243
Chen W Y C, Hou Q H, Zeilberger D. Automated discovery and proof of congruence theorems for partial sums of combinatorial sequences. J Difference Equ Appl, 2016, 22(6): 780–788
Chen W Y C, Li N Y, Shapiro L W, Yan S H F. Matrix identities on weighted partial Motzkin paths. European J Combin, 2007, 28(4): 1196–1207
Courtiel J, Melczer S, Mishna M et al. Weighted lattice walks and universality classes. J Combin Theory Ser A, 2017, 152: 255–302
Deng L H, Deng Y P, Shaporo L W. The Riordan group and symmetric lattice paths. J Shandong Univ Nat Sci, 2015, 50(4): 82–89, 94 (in Chinese)
Deng Y P. Lattice paths and permutations with forbidden patterns. Ph D Thesis, Tianjin: Nankai Univ, 2004
Drmota M. Lecture on “Positive catalytic and non-catalytic polynomial systems of equations”, Lattice Walks at the Interface of Algebra. Analysis and Combinatorics, BIRS, Banff, Sep 18–22, 2017
Du R R X, Yu K. Refinements of two identities on (n,m)-Dyck paths. Adv in Appl Math, 2018, 97: 54–63
Erickson M, Fernando S, Tran K. Enumerating rook and queen paths. Bull Inst Combin Appl, 2010, 60: 37–48
Erusalimskiy I M. Graph lattice: random walk and combinatorial identities. Bol Soc Mat Mex (3), 2016, 22(2): 329-335
Eu S-P, Fu T-S, Yeh Y-N. Refined Chung-Feller theorems for lattice paths. J Combin Theory Ser A, 2005, 112(1): 143–162
Feng J S. Sequence A277248. In: OEIS (On-Line Encyclopedia of Integer Sequences), 2016
Feng J S. A Hessenberg determinant of Pascal’s triangle and Catalan numbers. 2020, arXiv: 1909.00611v2
Feng X, Zhang L Z, Zhang M Z. Enumeration of perfect matchings of lattice graphs by Pfaffians. Appl Math Comput, 2018, 338: 412–420
Flajolet P, Sedgewick R. Analytic Combinatorics. Cambridge: Cambridge Univ Press, 2009
Gessel I M, Viennot G. Binomial determinants, paths, and hook length formulae. Adv Math, 1985, 58(3): 300–321
Gessel I M, Viennot G. Determinants, paths, and plane partitions. 1989
Ghorpade S R, Krattenthaler C. The Hilbert series of Pfaffian rings. In: Algebra, Arithmetic and Geometry with Applications (West Lafayette, IN, 2000), Berlin: Springer, 2004, 337–356
Guo V J W, Wang X X. A Chung-Feller theorem for lattice paths with respect to cyclically shifting boundaries. J Algebraic Combin, 2019, 50(2): 119–126
Hou Q H, Mansour T. Kernel method and linear recurrence system. J Comput Appl Math, 2008, 216(1): 227–242
Janse van Rensburg E J, Ye L. Forces in square lattice directed paths in a wedge. J Phys A, 2005, 38(40): 8493–8503
Jin E Y, Nebel M E. A combinatorial proof of the recurrence for rook paths. Electron J Combin, 2012, 19(1): Paper 59 (10 pp)
Kauers M, Zeilberger D. The computational challenge of enumerating high-dimensional rook walks. Adv in Appl Math, 2011, 47(4): 813–819
King R C, Welsh T A, van Willigenburg S J. Schur positivity of skew Schur function differences and applications to ribbons and Schubert classes. J Algebraic Combin, 2008, 28(1): 139–167
Koroljuk V S. On the discrepancy of empiric distributions for the case of two independent samples. Izvestiya Akad Nauk SSSR Ser Mat, 1955, 19: 81–96
Krattenthaler C. Lattice path enumertation. In: Bóna M, ed. Handbook of Enumerative Combinatorics. Discrete Math Appl (Boca Raton). Boca Raton: CRC Press, 2015, 589–678
Kung J P S, de Mier A. Catalan lattice paths with rook, bishop and spider steps. J Combin Theory Ser A, 2013, 120(2): 379–389
Kurkova I, Raschel K. On the functions counting walks with small steps in the quarter plane. Publ Math Inst Hautes Etudes Sci, 2012, 116: 69–114
Laferrière D F. Classification of walks in wedges. M S Thesis. Burnaby: Simon Fraser Univ, 2007
Lu Q L. Enumeration of k-colored skew Dyck path. J East China Normal Univ Nat Sci, 2015, (3): 31–37 (in Chinese)
Ma J, Yeh Y-N. Refinements of (n, m)-Dyck paths. European J Combin, 2011, 32(1): 92–99
Ma S M, Yeh Y-N. Eulerian polynomials, Stirling permutations of the second kind and perfect matchings. Electron J Combin, 2017, 24(4): Paper No 4.27 (18 pp)
Macdonald I G. Symmetric Functions and Hall Polynomials. 2nd Ed. New York: Oxford Univ Press, 1995
Macdonald I G. Orthogonal polynomials associated with root systems. Sém Lothar Combin, 2000/2001, 45: Art B45a (40 pp)
Melczer S, Mishna M. Asymptotic lattice path enumeration using diagonals. Algorithmica, 2016, 75(4): 782–811
Melczer S, Wilson M C. Asymptotics of lattice walks via analytic combinatorics in several variables. In: 28th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2016), DMTCS Proc, Vol BC. Nancy: Assoc Discrete Math Theor Comput Sci, 2016, 863–874
Merlini D, Sprugnoli R, Verri M C. The tennis ball problem. J Combin Theory Ser A, 2002, 99(2): 307–344
Prodinger H. Prodinger H. The kernel method: a collection of examples. Sém Lothar Combin, 2003/2004, 50: Art B50f (19 pp)
Stanley R P. Enumerative Combinatorics. Vol 2. Cambridge: Cambridge Univ Press, 1999
Stanley R P. Enumerative Combinatorics. Vol 1. 2nd Ed. Cambridge: Cambridge Univ Press, 2012
Stanley R P. Catalan Numbers. New York: Cambridge University Press, 2015
Van Willigenburg S V. The shuffle conjecture. Bull Amer Math Soc (N S), 2020, 57(1): 77–89
Wallner M. Combinatorics of lattice paths and tree-like structures. Ph D Thesis. Vienna: Vienna University of Technology, 2016
Wang Y, Yang A L B. Total positivity of Narayana matrices. Discrete Math, 2018, 341(5): 1264–1269
Wang Y, Xin G C. Hankel determinants for convolution powers of Catalan numbers. Discrete Math, 2019, 342(9): 2694–2716
Xu S J, Zhang H P, Cai J Z. Complete forcing numbers of catacondensed hexagonal systems. J Comb Optim, 2015, 29(4): 803–814
Yan S H F, Zhang Y Q. On lattice paths with four types of steps. Graphs Combin, 2015, 31(4): 1077–1084
Yang S L, Dong Y N, Yang L, Yin J. Half of a Riordan array and restricted lattice paths. Linear Algebra Appl, 2018, 537: 1–11
Zhang Y, Lu M. d-matching in 3-uniform hypergraphs. Discrete Math, 2018, 341(3): 748–758
Zhang Z Z, Li X Q. Mock theta functions in terms of q-hypergeometric double sums. Int J Number Theory, 2018, 14(6): 1715–1728
Zhao J J Y. Koroljuk’s formula for counting lattice paths revisited. Util Math, 2018, 107: 207–222
Acknowledgements
This paper was supported by the National Natural Science Foundation of China (Grant No. 11571155).
Author information
Authors and Affiliations
Corresponding author
Additional information
Translated from Advances in Mathematics (China), 2022, 51(3): 385–399
Rights and permissions
About this article
Cite this article
Feng, J., Wang, X., Gao, X. et al. The research and progress of the enumeration of lattice paths. Front. Math 17, 747–766 (2022). https://doi.org/10.1007/s11464-022-1031-0
Published:
Issue Date:
DOI: https://doi.org/10.1007/s11464-022-1031-0