The research and progress of the enumeration of lattice paths

doi:10.1007/s11464-022-1031-0

Front. Math. China

2022, Vol. 17

Issue (5) : 747-766 https://doi.org/10.1007/s11464-022-1031-0

SURVEY ARTICLE

The research and progress of the enumeration of lattice paths

Jishe FENG¹(

), Xiaomeng WANG², Xiaolu GAO², Zhuo PAN²

¹. School of Mathematics and Statistics, Longdong University, Qingyang 745000, China
². School of Mathematics and Statistics, Lanzhou University, Lanzhou 730000, China

Download: PDF(1805 KB) HTML
Export: BibTeX | EndNote | Reference Manager | ProCite | RefWorks

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.

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

Corresponding Author(s): Jishe FENG

Online First Date: 22 December 2022 Issue Date: 28 December 2022

Cite this article:

Jishe FENG,Xiaomeng WANG,Xiaolu GAO, et al. The research and progress of the enumeration of lattice paths[J]. Front. Math. China, 2022, 17(5): 747-766.

URL:

https://academic.hep.com.cn/fmc/EN/10.1007/s11464-022-1031-0
https://academic.hep.com.cn/fmc/EN/Y2022/V17/I5/747

kind	step	start point	destination point	The first few terms
Catalan $C n$	$(1, 0), (0, 1)$	$(0, 0)$	$(n, n)$	$1, 1, 2, 5, 14, 42, 132$
Large Schröder $S n$	$(1, 0), (0, 1), (1, 1)$	$(0, 0)$	$(n, n)$	$1, 2, 6, 22, 90, 394, 1806$

Tab.1 Lattice paths of Catalan and large Schröder

kind	step	start point	destination point	The first few terms
Catalan $C n$	$(1, 1), (1, − 1)$	$(0, 0)$	$(2 n, 0)$	$1, 1, 2, 5, 14, 42, 132$
Motzkin $M n$	$(1, 1), (1, − 1), (1, 0)$	$(0, 0)$	$(n, 0)$	$1, 1, 2, 4, 9, 21, 51$
Large Schröder $S n$	$(1, 1), (1, − 1), (2, 0)$	$(0, 0)$	$(2 n, 0)$	$1, 2, 6, 22, 90, 394, 1806$

Tab.2 Lattice paths of Catalan, Motzkin and large Schröder

Fig.1 (a) Catalan number and corresponding numbers of the lattice paths from

(0, 0)

(5, 5)

; (b) the lattice is transformed symmetrically along the line

y = x

, and the scale is enlarged by

2

, when the coordinate system is rotated counterclockwise

45 ∘

, the corresponding Catalan numbers and the number of lattice paths from

(0, 0)

(10, 0)

are obtained; (c) is the same as (b), large Schröder number is the number of lattice paths which starting

(0, 0)

(10, 0)

; (d) is the same as (b), Motzkin number is the number of lattice paths which starting

(0, 0)

(7, 0)

, where the interact point marked o, that means they don’t intersect here, no marked o, that means they intersect here.

kind	recurrence relation	initial condition
Catalan	$C (h, k) = C (h − 1, k) + C (h, k − 1)$	$C (i, 0) = 1$ , $i = 0, 1, 2, ?$
Catalan	$C (h, k) = C (h − 1, k − 1) + C (h − 1, k + 1)$	$C (i, i) = 1$ , $i = 0, 1, 2, ?$
Large Schröder	$S (h, k) = S (h − 1, k − 1) + S (h − 1, k − 1) + S (h − 2, k)$	$S (i, i) = 1$ , $i = 0, 1, 2, ?$
Motzkin	$M (h, k) = M (h − 1, k − 1) + M (h − 1, k − 1) + M (h − 1, k)$	$M (i, i) = 1$ , $i = 0, 1, 2, ?$

Tab.3 The recurrence relations and initial conditions

Fig.2 The specified lattice path

{(1, 2) (2, 2) (3, 2) (4, 6) (5, 6) (6, 6)},

which length is

n = 6

in the area enclosed by two lattice paths

{(1, 3) (2, 5) (3, 7) (4, 8) (5, 8) (6, 8)}

and

{(1, 0) (2, 1) (3, 1) (4, 4) (5, 5) (6, 5)}

Fig.3 Four disjoint lattice paths with definite starting and ending points and details of the number of solutions from each starting point to the end point

Fig.4 A perfect matching of

A = {1, 2, 3, 4, 5, 6}

Fig.5 Bijection between 3-disjoint lattice path and 6-semistandard Young tableax and corresponding weight expression

ω (T) = x 14 x 2 x 3 x 4 x 5 x 6

1	C Banderier, P Flajolet. Basic analytic combinatorics of directed lattice paths. Theoret Comput Sci 2002; 281(1/2): 37–80
2	C BanderierC KrattenthalerA Krinik, 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
3	C Banderier, S Schwer. Why Delannoy numbers?. J Statist Plann Inference 2005; 135(1): 40–54
4	C BanderierM Wallner. Local time for lattice paths and the associated limit laws. arXiv: 1805.09065
5	J P Bell, S S Chen. Power series with coefficients from a finite set. J Combin Theory Ser A 2017; 151: 241–253
6	A T Benjamin, N T Cameron. Counting on determinants. Amer Math Monthly 2005; 112(6): 481–492
7	A Bostan, M Bousquet-Mélou, M Kauers. et al.. On 3-dimensional lattice walks confined to the positive octant. Ann Comb 2016; 20(4): 661–704
8	A Bostan, F Chyzak, M van Hoeij. et al.. Hypergeometric expressions for generating functions of walks with small steps in the quarter plane. European J Combin 2017; 61: 242–275
9	A BostanF ChyzakM van Hoeij, et al.. Explicit formula for the generating series of diagonal 3D rook paths. Sém Lothar Combin, 2011/2012, 66: Art B66a (27 pp)
10	A BostanM Kauers. 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	M Bousquet-Mélou. An elementary solution of Gessel’s walks in the quadrant. Adv Math 2016; 303: 1171–1189
12	M Bousquet-MélouM Mishna. Walks with small steps in the quarter plane. In: Algorithmic Probability and Combinatorics. Contemp Math, Vol 520. Providence: AMS, 2010, 1–39
13	M Bousquet-Mélou, M Petkovšek. Linear recurrences with constant coefficients: the multivariate case. Discrete Math 2000; 225(1/2/3): 51–75
14	M Bousquet-Mélou, M Petkovšek. Walks confined in a quadrant are not always D-finite. Theoretical Computer Science 2003; 307(2): 257–276
15	R Brak, J Essam, J Osborn. et al.. Lattice paths and the constant term. J Phys Conf Ser 2006; 42(1): 47–58
16	S Carrozza, A Tanasa. Pfaffians and nonintersecting paths in graphs with cycles: Grassmann algebra methods. Adv in Appl Math 2018; 93: 108–120
17	O A Chalykh. Macdonald polynomials and algebraic integrability. Adv Math 2002; 166(2): 193–259
18	S S ChenF ChyzakR Y Feng, et al.. On the existence of telescopers for mixed hypergeometric terms. J Symbolic Comput. 2015, 68: Part 1, 1–26
19	W Y C Chen, E Y P Deng, R R X Du. Reduction of m-regular noncrossing partitions. European J Combin 2005; 26(2): 237–243
20	W Y C Chen, Q H Hou, D Zeilberger. Automated discovery and proof of congruence theorems for partial sums of combinatorial sequences. J Difference Equ Appl 2016; 22(6): 780–788
21	W Y C Chen, N Y Li, L W Shapiro, S H F Yan. Matrix identities on weighted partial Motzkin paths. European J Combin 2007; 28(4): 1196–1207
22	J Courtiel, S Melczer, M Mishna. et al.. Weighted lattice walks and universality classes. J Combin Theory Ser A 2017; 152: 255–302
23	L H Deng, Y P Deng, L W Shaporo. The Riordan group and symmetric lattice paths. J Shandong Univ Nat Sci 2015; 50(4): 82–89, 94
24	Y P Deng. Lattice paths and permutations with forbidden patterns. Ph D Thesis, Tianjin: Nankai Univ, 2004
25	M Drmota. 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	R R X Du, K Yu. Refinements of two identities on (n,m)-Dyck paths. Adv in Appl Math 2018; 97: 54–63
27	M Erickson, S Fernando, K Tran. Enumerating rook and queen paths. Bull Inst Combin Appl 2010; 60: 37–48
28	I M Erusalimskiy. Graph lattice: random walk and combinatorial identities. Bol Soc Mat Mex (3) 2016; 22(2): 329–335
29	S-P Eu, T-S Fu, Y-N Yeh. Refined Chung-Feller theorems for lattice paths. J Combin Theory Ser A 2005; 112(1): 143–162
30	J S Feng. Sequence A277248. In: OEIS (On-Line Encyclopedia of Integer Sequences), 2016
31	J S Feng. A Hessenberg determinant of Pascal’s triangle and Catalan numbers. 2020, arXiv: 1909.00611v2
32	X Feng, L Z Zhang, M Z Zhang. Enumeration of perfect matchings of lattice graphs by Pfaffians. Appl Math Comput 2018; 338: 412–420
33	P FlajoletR Sedgewick. Analytic Combinatorics. Cambridge: Cambridge Univ Press, 2009
34	I M Gessel, G Viennot. Binomial determinants, paths, and hook length formulae. Adv Math 1985; 58(3): 300–321
35	I M GesselG Viennot. Determinants, paths, and plane partitions. 1989
36	S R GhorpadeC Krattenthaler. The Hilbert series of Pfaffian rings. In: Algebra, Arithmetic and Geometry with Applications (West Lafayette, IN, 2000), Berlin: Springer, 2004, 337–356
37	V J W Guo, X X Wang. A Chung-Feller theorem for lattice paths with respect to cyclically shifting boundaries. J Algebraic Combin 2019; 50(2): 119–126
38	Q H Hou, T Mansour. Kernel method and linear recurrence system. J Comput Appl Math 2008; 216(1): 227–242
39	E J Janse van Rensburg, L Ye. Forces in square lattice directed paths in a wedge. J Phys A 2005; 38(40): 8493–8503
40	E Y Jin, M E Nebel. A combinatorial proof of the recurrence for rook paths. Electron J Combin 2012; 19(1): Paper 59 (10 pp)
41	M Kauers, D Zeilberger. The computational challenge of enumerating high-dimensional rook walks. Adv in Appl Math 2011; 47(4): 813–819
42	R C King, T A Welsh, S J van Willigenburg. Schur positivity of skew Schur function differences and applications to ribbons and Schubert classes. J Algebraic Combin 2008; 28(1): 139–167
43	V S Koroljuk. On the discrepancy of empiric distributions for the case of two independent samples. Izvestiya Akad Nauk SSSR Ser Mat 1955; 19: 81–96
44	C Krattenthaler. 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	J P S Kung, A de Mier. Catalan lattice paths with rook, bishop and spider steps. J Combin Theory Ser A 2013; 120(2): 379–389
46	I Kurkova, K Raschel. On the functions counting walks with small steps in the quarter plane. Publ Math Inst Hautes Etudes Sci 2012; 116: 69–114
47	D F Laferrière. Classification of walks in wedges. M S Thesis. Burnaby: Simon Fraser Univ, 2007
48	Q L Lu. Enumeration of k-colored skew Dyck path. J East China Normal Univ Nat Sci 2015; (3): 31–37
49	J Ma, Y-N Yeh. Refinements of (n, m)-Dyck paths. European J Combin 2011; 32(1): 92–99
50	S M Ma, Y-N Yeh. Eulerian polynomials, Stirling permutations of the second kind and perfect matchings. Electron J Combin 2017; 24(4): Paper No 4.27 (18 pp)
51	I G Macdonald. Symmetric Functions and Hall Polynomials. 2nd Ed. New York: Oxford Univ Press, 1995
52	I G Macdonald. Orthogonal polynomials associated with root systems. Sém Lothar Combin 2000/2001; 45: Art B45a (40 pp)
53	S Melczer, M Mishna. Asymptotic lattice path enumeration using diagonals. Algorithmica 2016; 75(4): 782–811
54	S MelczerM C Wilson. 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	D Merlini, R Sprugnoli, M C Verri. The tennis ball problem. J Combin Theory Ser A 2002; 99(2): 307–344
56	H Prodinger. Prodinger H. The kernel method: a collection of examples. Sém Lothar Combin 2003/2004; 50: Art B50f (19 pp)
57	R P Stanley. Enumerative Combinatorics. Vol 2. Cambridge: Cambridge Univ Press, 1999
58	R P Stanley. Enumerative Combinatorics. Vol 1. 2nd Ed. Cambridge: Cambridge Univ Press, 2012
59	R P Stanley. Catalan Numbers. New York: Cambridge University Press, 2015
60	S V Van Willigenburg. The shuffle conjecture. Bull Amer Math Soc (N S) 2020; 57(1): 77–89
61	M Wallner. Combinatorics of lattice paths and tree-like structures. Ph D Thesis. Vienna: Vienna University of Technology, 2016
62	Y Wang, A L B Yang. Total positivity of Narayana matrices. Discrete Math 2018; 341(5): 1264–1269
63	Y Wang, G C Xin. Hankel determinants for convolution powers of Catalan numbers. Discrete Math 2019; 342(9): 2694–2716
64	S J Xu, H P Zhang, J Z Cai. Complete forcing numbers of catacondensed hexagonal systems. J Comb Optim 2015; 29(4): 803–814
65	S H F Yan, Y Q Zhang. On lattice paths with four types of steps. Graphs Combin 2015; 31(4): 1077–1084
66	S L Yang, Y N Dong, L Yang, J Yin. Half of a Riordan array and restricted lattice paths. Linear Algebra Appl 2018; 537: 1–11
67	Y Zhang, M Lu. d-matching in 3-uniform hypergraphs. Discrete Math 2018; 341(3): 748–758
68	Z Z Zhang, X Q Li. Mock theta functions in terms of q-hypergeometric double sums. Int J Number Theory 2018; 14(6): 1715–1728
69	J J Y Zhao. Koroljuk’s formula for counting lattice paths revisited. Util Math 2018; 107: 207–222

[1]	Changqing XU. Fourier matrices and Fourier tensors[J]. Front. Math. China, 2021, 16(4): 1099-1115.
[2]	Hongmei HU, Naihong HU, Limeng XIA. Majid conjecture: quantum Kac-Moody algebras version[J]. Front. Math. China, 2021, 16(3): 727-747.
[3]	Mu-Fa CHEN, Zhi-Gang JIA, Hong-Kui PANG. Computing top eigenpairs of Hermitizable matrix[J]. Front. Math. China, 2021, 16(2): 345-379.
[4]	Saeed RAHMATI, Mohamed A. TAWHID. On intervals and sets of hypermatrices (tensors)[J]. Front. Math. China, 2020, 15(6): 1175-1188.
[5]	Mu-Fa CHEN. On spectrum of Hermitizable tridiagonal matrices[J]. Front. Math. China, 2020, 15(2): 285-303.
[6]	Xin LI, Jiming GUO, Zhiwen WANG. Minimal least eigenvalue of connected graphs of order n and size m = n + k (5≤k≤8)[J]. Front. Math. China, 2019, 14(6): 1213-1230.
[7]	Yanyan WANG. Determination of generalized exact boundary synchronization matrix for a coupled system of wave equations[J]. Front. Math. China, 2019, 14(6): 1339-1352.
[8]	Kinkar Chandra DAS, Huiqiu LIN, Jiming GUO. Distance signless Laplacian eigenvalues of graphs[J]. Front. Math. China, 2019, 14(4): 693-713.
[9]	Mu-Fa CHEN, Yue-Shuang LI. Development of powerful algorithm for maximal eigenpair[J]. Front. Math. China, 2019, 14(3): 493-519.
[10]	Mu-Fa CHEN. Hermitizable, isospectral complex matrices or differential operators[J]. Front. Math. China, 2018, 13(6): 1267-1311.
[11]	Tai Keun KWAK, Yang LEE, Young Joo SEO. Some remarks on one-sided regularity[J]. Front. Math. China, 2018, 13(4): 833-847.
[12]	Zhihe LIANG. *Super (a, d)-edge-antimagic total labelings of complete bipartite graphs*[J]. Front. Math. China, 2018, 13(1): 129-146.
[13]	Jie WEN, Qin NI, Wenhuan ZHU. Rank-r decomposition of symmetric tensors[J]. Front. Math. China, 2017, 12(6): 1339-1355.
[14]	Mu-Fa CHEN. Efficient initials for computing maximal eigenpair[J]. Front. Math. China, 2016, 11(6): 1379-1418.
[15]	Chan Yong HONG,Nam Kyun KIM,Tai Keun KWAK,Yang LEE. On extensions of matrix rings with skew Hochschild 2-cocycles[J]. Front. Math. China, 2016, 11(4): 869-900.

Viewed

Full text

Abstract

Cited

Shared

Discussed