The research and progress of the enumeration of lattice paths

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.

Graphical abstract

Keywords

Enumeration of lattice paths / generating function / matrix / family of lattice paths / symmetric function

References

[1] Banderier C, Flajolet P. Basic analytic combinatorics of directed lattice paths. Theoret Comput Sci 2002; 281(1/2): 37–80

[2] BanderierCKrattenthaler CKrinikA, . 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

[3] Banderier C, Schwer S. Why Delannoy numbers?. J Statist Plann Inference 2005; 135(1): 40–54

[4] BanderierCWallner M. Local time for lattice paths and the associated limit laws. arXiv: 1805.09065

[5] Bell J P, Chen S S. Power series with coefficients from a finite set. J Combin Theory Ser A 2017; 151: 241–253

[6] Benjamin A T, Cameron N T. Counting on determinants. Amer Math Monthly 2005; 112(6): 481–492

[7] Bostan A, Bousquet-Mélou M, Kauers M. . On 3-dimensional lattice walks confined to the positive octant. Ann Comb 2016; 20(4): 661–704

[8] Bostan A, Chyzak F, van Hoeij M. . Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. European J Combin 2017; 61: 242–275

[9] BostanAChyzak Fvan HoeijM, . Explicit formula for the generating series of diagonal 3D rook paths. Sém Lothar Combin, 2011/2012, 66: Art B66a (27 pp)

[10] BostanAKauers 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

[11] Bousquet-Mélou M. An elementary solution of Gessel’s walks in the quadrant. Adv Math 2016; 303: 1171–1189

[12] Bousquet-MélouMMishnaM. Walks with small steps in the quarter plane. In: Algorithmic Probability and Combinatorics. Contemp Math, Vol 520. Providence: AMS, 2010, 1–39

[13] Bousquet-Mélou M, Petkovšek M. Linear recurrences with constant coefficients: the multivariate case. Discrete Math 2000; 225(1/2/3): 51–75

[14] 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

[15] Brak R, Essam J, Osborn J. . Lattice paths and the constant term. J Phys Conf Ser 2006; 42(1): 47–58

[16] Carrozza S, Tanasa A. Pfaffians and nonintersecting paths in graphs with cycles: Grassmann algebra methods. Adv in Appl Math 2018; 93: 108–120

[17] Chalykh O A. Macdonald polynomials and algebraic integrability. Adv Math 2002; 166(2): 193–259

[18] ChenS SChyzak FFengR Y, . On the existence of telescopers for mixed hypergeometric terms. J Symbolic Comput. 2015, 68: Part 1, 1–26

[19] 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

[20] 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

[21] 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

[22] Courtiel J, Melczer S, Mishna M. . Weighted lattice walks and universality classes. J Combin Theory Ser A 2017; 152: 255–302

[23] 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

[24] DengY P. Lattice paths and permutations with forbidden patterns. Ph D Thesis, Tianjin: Nankai Univ, 2004

[25] DrmotaM. 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

[26] Du R R X, Yu K. Refinements of two identities on (n,m)-Dyck paths. Adv in Appl Math 2018; 97: 54–63

[27] Erickson M, Fernando S, Tran K. Enumerating rook and queen paths. Bull Inst Combin Appl 2010; 60: 37–48

[28] Erusalimskiy I M. Graph lattice: random walk and combinatorial identities. Bol Soc Mat Mex (3) 2016; 22(2): 329–335

[29] 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

[30] FengJ S. Sequence A277248. In: OEIS (On-Line Encyclopedia of Integer Sequences), 2016

[31] FengJ S. A Hessenberg determinant of Pascal’s triangle and Catalan numbers. 2020, arXiv: 1909.00611v2

[32] Feng X, Zhang L Z, Zhang M Z. Enumeration of perfect matchings of lattice graphs by Pfaffians. Appl Math Comput 2018; 338: 412–420

[33] FlajoletPSedgewick R. Analytic Combinatorics. Cambridge: Cambridge Univ Press, 2009

[34] Gessel I M, Viennot G. Binomial determinants, paths, and hook length formulae. Adv Math 1985; 58(3): 300–321

[35] GesselI MViennot G. Determinants, paths, and plane partitions. 1989

[36] GhorpadeS RKrattenthaler C. The Hilbert series of Pfaffian rings. In: Algebra, Arithmetic and Geometry with Applications (West Lafayette, IN, 2000), Berlin: Springer, 2004, 337–356

[37] 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

[38] Hou Q H, Mansour T. Kernel method and linear recurrence system. J Comput Appl Math 2008; 216(1): 227–242

[39] Janse van Rensburg E J, Ye L. Forces in square lattice directed paths in a wedge. J Phys A 2005; 38(40): 8493–8503

[40] 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)

[41] Kauers M, Zeilberger D. The computational challenge of enumerating high-dimensional rook walks. Adv in Appl Math 2011; 47(4): 813–819

[42] 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

[43] 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

[44] KrattenthalerC. Lattice path enumertation. In: Bóna M, ed. Handbook of Enumerative Combinatorics. Discrete Math Appl (Boca Raton). Boca Raton: CRC Press, 2015, 589–678

[45] 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

[46] 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

[47] LaferrièreD F. Classification of walks in wedges. M S Thesis. Burnaby: Simon Fraser Univ, 2007

[48] Lu Q L. Enumeration of k-colored skew Dyck path. J East China Normal Univ Nat Sci 2015; (3): 31–37

[49] Ma J, Yeh Y-N. Refinements of (n, m)-Dyck paths. European J Combin 2011; 32(1): 92–99

[50] 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)

[51] MacdonaldI G. Symmetric Functions and Hall Polynomials. 2nd Ed. New York: Oxford Univ Press, 1995

[52] Macdonald I G. Orthogonal polynomials associated with root systems. Sém Lothar Combin 2000/2001; 45: Art B45a (40 pp)

[53] Melczer S, Mishna M. Asymptotic lattice path enumeration using diagonals. Algorithmica 2016; 75(4): 782–811

[54] MelczerSWilson 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

[55] Merlini D, Sprugnoli R, Verri M C. The tennis ball problem. J Combin Theory Ser A 2002; 99(2): 307–344

[56] Prodinger H. Prodinger H. The kernel method: a collection of examples. Sém Lothar Combin 2003/2004; 50: Art B50f (19 pp)

[57] StanleyR P. Enumerative Combinatorics. Vol 2. Cambridge: Cambridge Univ Press, 1999

[58] StanleyR P. Enumerative Combinatorics. Vol 1. 2nd Ed. Cambridge: Cambridge Univ Press, 2012

[59] StanleyR P. Catalan Numbers. New York: Cambridge University Press, 2015

[60] Van Willigenburg S V. The shuffle conjecture. Bull Amer Math Soc (N S) 2020; 57(1): 77–89

[61] WallnerM. Combinatorics of lattice paths and tree-like structures. Ph D Thesis. Vienna: Vienna University of Technology, 2016

[62] Wang Y, Yang A L B. Total positivity of Narayana matrices. Discrete Math 2018; 341(5): 1264–1269

[63] Wang Y, Xin G C. Hankel determinants for convolution powers of Catalan numbers. Discrete Math 2019; 342(9): 2694–2716

[64] Xu S J, Zhang H P, Cai J Z. Complete forcing numbers of catacondensed hexagonal systems. J Comb Optim 2015; 29(4): 803–814

[65] Yan S H F, Zhang Y Q. On lattice paths with four types of steps. Graphs Combin 2015; 31(4): 1077–1084

[66] 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

[67] Zhang Y, Lu M. d-matching in 3-uniform hypergraphs. Discrete Math 2018; 341(3): 748–758

[68] 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

[69] 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).

RIGHTS & PERMISSIONS

2022 Higher Education Press 2022