SURVEY ARTICLE

The research and progress of the enumeration of lattice paths

  • Jishe FENG , 1 ,
  • Xiaomeng WANG 2 ,
  • Xiaolu GAO 2 ,
  • Zhuo PAN 2
Expand
  • 1. School of Mathematics and Statistics, Longdong University, Qingyang 745000, China
  • 2. School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China

Published date: 15 Oct 2022

Copyright

2022 Higher Education Press 2022

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.

Cite this article

Jishe FENG , Xiaomeng WANG , Xiaolu GAO , Zhuo PAN . The research and progress of the enumeration of lattice paths[J]. Frontiers of Mathematics in China, 2022 , 17(5) : 747 -766 . DOI: 10.1007/s11464-022-1031-0

Acknowledgements

This paper was supported by the National Natural Science Foundation of China (Grant No. 11571155).
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

Outlines

/