×

Enumeration of lattice paths with infinite types of steps and the Chung-Feller property. (English) Zbl 1469.05012

Summary: In this paper we consider the lattice paths that go from the origin to a point on the right half of the plane with step set \(S = \{ U_i = (1 + i, 1 - i) \mid i \geq 0 \} \bigcup \{ V_i = (i, - i) \mid i \geq 1 \}\) such that the step \(U_i\) is assigned with weight \(u_i\) and the step \(V_i\) is assigned with weight \(v_i\) for \(i \geq 1\) except that the step \(U_0 = (1, 1)\) is assigned with weight 1. Let \(G(n, k)\) be the set of all lattice paths ending at the point \((n, 2 k - n)\) and \(G_{n , k} = | G(n, k) |\), and let \(U(n, k)\) (resp. \(V(n, k)\)) be the set of all lattice paths (resp. nonnegative lattice paths) ending at \((2 n - k, k)\) and \(U_{n , k} = | U(n, k) |\) (resp. \( V_{n , k} = | V(n, k) |\)). We will show that \(( G_{n , k} )_{n , k \in \mathbb{N}}\), \(( U_{n , k} )_{n , k \in \mathbb{N}}\) and \(( V_{n , k} )_{n , k \in \mathbb{N}}\) are all Riordan arrays. Correlations between these Riordan arrays are studied. Consequently, a new Chung-Feller type property is obtained, and the bijective proof is provided. We also list numerous interesting examples.

MSC:

05A15 Exact enumeration problems, generating functions
05A19 Combinatorial identities, bijective combinatorics

Software:

OEIS
PDFBibTeX XMLCite
Full Text: DOI

References:

[1] Barry, P., On the central coefficients of Riordan matrices, J. Integer Seq., 16 (2013), Article 13.5.1 · Zbl 1310.11032
[2] Baril, J-L.; Kirgizov, S.; Petrossian, A., Enumeration of Łukasiewicz paths modulo some patterns, Discrete Math., 342, 997-1005 (2019) · Zbl 1405.05007
[3] Chen, Y. M., The Chung-Feller theorem revisited, Discrete Math., 308, 1328-1329 (2008) · Zbl 1132.05004
[4] Cheon, G. S.; Kim, H.; Shapiro, L. W., Combinatorics of Riordan arrays with identical A and Z sequences, Discrete Math., 312, 2040-2049 (2012) · Zbl 1243.05007
[5] Chung, K. L.; Feller, W., On fluctuations in coin tossing, Proc. Natl. Acad. Sci. USA, 35, 605-608 (1949) · Zbl 0037.36310
[6] Coker, C., Enumerating a class of lattice paths, Discrete Math., 271, 13-28 (2003) · Zbl 1027.05002
[7] Comtet, L., Advanced Combinatorics (1974), D. Reidel Publishing Co.: D. Reidel Publishing Co. Dordrecht · Zbl 0283.05001
[8] Dziemiańczuk, M., Counting lattice paths with four types of steps, Graphs Comb., 30, 1427-1452 (2014) · Zbl 1306.05007
[9] Eu, S. P.; Fu, T. S.; Yeh, Y. N., Refined Chung-Feller theorems for lattice paths, J. Comb. Theory, Ser. A, 112, 143-162 (2005) · Zbl 1072.05002
[10] Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1165.05001
[11] He, T. X.; Sprugnoli, R., Sequence characterization of Riordan arrays, Discrete Math., 309, 3962-3974 (2009) · Zbl 1228.05014
[12] Huh, J.; Park, S., Generalized small Schröder numbers, Electron. J. Comb., 22, Article P3.14 pp. (2015) · Zbl 1327.05017
[13] Humphreys, K., A history and a survey of lattice path enumeration, J. Stat. Plan. Inference, 140, 2237-2254 (2010) · Zbl 1204.05015
[14] Kung, J. P.S.; Mier, A., Catalan lattice paths with rook, bishop and spider steps, J. Comb. Theory, Ser. A, 120, 379-389 (2013) · Zbl 1256.05008
[15] Lehner, F., Cumulants, lattice paths, and orthogonal polynomials, Discrete Math., 270, 177-191 (2003) · Zbl 1026.05005
[16] Luzón, A.; Merlini, D.; Morón, M.; Sprugnoli, R., Identities induced by Riordan arrays, Linear Algebra Appl., 436, 631-647 (2011) · Zbl 1232.05011
[17] Ma, J.; Yeh, Y. N., Refinements of \((n, m)\)-Dyck paths, Eur. J. Comb., 32, 92-99 (2011) · Zbl 1201.05008
[18] Manes, K.; Sapounakis, A.; Tasoulas, I.; Tsikouras, P., Strings of length 3 in grand Dyck paths and the Chung-Feller property, Electron. J. Comb., 19 (2012), P2 · Zbl 1243.05021
[19] Merlini, D.; Rogers, D. G.; Sprugnoli, R.; Verri, M. C., On some alternative characterizations of Riordan arrays, Can. J. Math., 49, 301-320 (1997) · Zbl 0886.05013
[20] Nkwanta, A.; Shapiro, L. W., Pell walks and Riordan matrices, Fibonacci Q., 43, 170-180 (2005) · Zbl 1074.60053
[21] Park, Y.; Park, S., Enumeration of generalized lattice paths by string types, peaks, and ascents, Discrete Math., 339, 2652-2659 (2016) · Zbl 1339.05022
[22] Peart, P.; Woan, W., A divisibility property for a subgroup of Riordan matrices, Discrete Appl. Math., 98, 255-263 (2000) · Zbl 0944.05016
[23] Ramírez, J. L.; Sirvent, V. F., A generalization of the k-bonacci sequence from Riordan arrays, Electron. J. Comb., 22, Article P1.38 pp. (2015) · Zbl 1308.11016
[24] Sloane, N. J.A., On-line encyclopedia of integer sequences (OEIS) (2021), Published electronically at
[25] Shapiro, L. W.; Getu, S.; Woan, W. J.; Woodson, L., The Riordan group, Discrete Appl. Math., 34, 229-239 (1991) · Zbl 0754.05010
[26] Song, C., The generalized Schröder theory, Electron. J. Comb., 12, Article R53 pp. (2005) · Zbl 1077.05010
[27] Sprugnoli, R., Riordan arrays and combinatorial sums, Discrete Math., 132, 267-290 (1994) · Zbl 0814.05003
[28] Stanley, R. P., Enumerative Combinatorics (Vol. 2) (1999), Cambridge Univ. Press: Cambridge Univ. Press Cambridge/New York · Zbl 0928.05001
[29] Woan, W., A relation between restricted and unrestricted weighted Motzkin paths, J. Integer Seq., 9 (2006), Article 06.1.7 · Zbl 1101.05008
[30] Woan, W., Uniform partitions of lattice paths and Chung-Feller generalizations, Am. Math. Mon., 108, 556-559 (2001) · Zbl 0988.05013
[31] Yan, H. F.; Zhang, Y., On lattice paths with four types of steps, Graphs Comb., 31, 1077-1084 (2015) · Zbl 1317.05009
[32] Yang, L.; Yang, S. L., A Chung-Feller property for the generalized Schröder paths, Discrete Math., 343, Article 111826 pp. (2020) · Zbl 1435.05009
[33] Yang, S. L.; Zheng, S. N.; Yuan, S. P.; He, T. X., Schröder matrix as inverse of Delannoy matrix, Linear Algebra Appl., 439, 3605-3614 (2013) · Zbl 1283.15098
[34] Yang, S. L.; Xu, Y. X.; Gao, X., On the half of a Riordan array, Ars Comb., 133, 407-422 (2017) · Zbl 1424.05005
[35] Yang, S. L.; Dong, Y. N.; Yang, L.; Yin, J., Half of a Riordan array and restricted lattice paths, Linear Algebra Appl., 537, 1-11 (2018) · Zbl 1373.05007
This reference list is based on information provided by the publisher or from digital mathematics libraries. Its items are heuristically matched to zbMATH identifiers and may contain data conversion errors. In some cases that data have been complemented/enhanced by data from zbMATH Open. This attempts to reflect the references listed in the original paper as accurately as possible without claiming completeness or a perfect matching.