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.

Key words： Enumeration of lattice paths; generating function; matrix; family of lattice paths; symmetric function

Acknowledgements

This paper was supported by the National Natural Science Foundation of China (Grant No. 11571155).

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