Czechoslovak Mathematical Journal, Vol. 70, No. 2, pp. 411-433, 2020


Generalized Schröder matrices arising from enumeration of lattice paths

Lin Yang, Sheng-Liang Yang, Tian-Xiao He

Received July 26, 2018.   Published online December 5, 2019.

Abstract:  We introduce a new family of generalized Schröder matrices from the Riordan arrays which are obtained by counting of the weighted lattice paths with steps $E = (1, 0)$, $ D = (1,1)$, $ N= (0,1)$, and $ D' = (1,2)$ and not going above the line $y=x$. We also consider the half of the generalized Delannoy matrix which is derived from the enumeration of these lattice paths with no restrictions. Correlations between these matrices are considered. By way of illustration, we give several examples of Riordan arrays of combinatorial interest. In addition, we find some new interesting identities.
Keywords:  Riordan array; lattice path; Delannoy matrix; Schröder number; Schröder matrix
Classification MSC:  05A15, 05A19, 15A24, 11B83
DOI:  10.21136/CMJ.2019.0348-18


References:
[1] M. Aigner: Enumeration via ballot numbers. Discrete Math. 308 (2008), 2544-2563. DOI 10.1016/j.disc.2007.06.012 | MR 2410460 | Zbl 1147.05002
[2] P. Barry: On the central coefficients of Riordan matrices. J. Integer Seq. 16 (2013), Article 13.5.1, 12 pages. MR 3065330 | Zbl 1310.11032
[3] J. Bonin, L. Shapiro, R. Simion: Some $q$-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths. J. Stat. Plann. Inference 34 (1993), 35-55. DOI 10.1016/0378-3758(93)90032-2 | MR 1209988 | Zbl 0783.05008
[4] X. Chen, H. Liang, Y. Wang: Total positivity of Riordan arrays. Eur. J. Comb. 46 (2015), 68-74. DOI 10.1016/j.ejc.2014.11.009 | MR 3305345 | Zbl 1307.05010
[5] G.-S. Cheon, H. Kim, L. W. Shapiro: Combinatorics of Riordan arrays with identical $A$ and $Z$ sequences. Discrete Math. 312 (2012), 2040-2049. DOI 10.1016/j.disc.2012.03.023 | MR 2920864 | Zbl 1243.05007
[6] L. Comtet: Advanced Combinatorics: The Art of Finite and Infinite Expansions. D. Reidel Publishing, Dordrecht (1974). DOI 10.1007/978-94-010-2196-8 | MR 0460128 | Zbl 0283.05001
[7] E. Deutsch: A bijective proof of the equation linking the Schröder numbers, large and small. Discrete Math. 241 (2001), 235-240. DOI 10.1016/S0012-365X(01)00122-4 | MR 1861420 | Zbl 0992.05010
[8] E. Deutsch, E. Munarini, S. Rinaldi: Skew Dyck paths. J. Stat. Plann. Inference 140 (2010), 2191-2203. DOI 10.1016/j.jspi.2010.01.015 | MR 2609478 | Zbl 1232.05010
[9] M. Dziemiańczuk: Counting lattice paths with four types of steps. Graphs Comb. 30 (2014), 1427-1452. DOI 10.1007/s00373-013-1357-1 | MR 3268642 | Zbl 1306.05007
[10] T.-X. He: Parametric Catalan numbers and Catalan triangles. Linear Algebra Appl. 438 (2013), 1467-1484. DOI 10.1016/j.laa.2012.10.001 | MR 2997825 | Zbl 1257.05003
[11] K. Humphreys: A history and a survey of lattice path enumeration. J. Stat. Plann. Inference 140 (2010), 2237-2254. DOI 10.1016/j.jspi.2010.01.020 | MR 2609483 | Zbl 1204.05015
[12] A. Luzón, D. Merlini, M. Morón, R. Sprugnoli: Identities induced by Riordan arrays. Linear Algebra Appl. 436 (2011), 631-647. DOI 10.1016/j.laa.2011.08.007 | MR 2854896 | Zbl 1232.05011
[13] T. Mansour, M. Schork, Y. Sun: Motzkin numbers of higher ranks: Generating function and explicit expression. J. Integer Seq. 10 (2007), Article 07.7.4, 11 pages. MR 2322499 | Zbl 1141.05308
[14] D. Merlini: Proper generating trees and their internal path length. Discrete Appl. Math. 156 (2008), 627-646. DOI 10.1016/j.dam.2007.08.051 | MR 2397210 | Zbl 1136.05002
[15] D. Merlini, D. G. Rogers, R. Sprugnoli, M. C. Verri: On some alternative characterizations of Riordan arrays. Can. J. Math. 49 (1997), 301-320. DOI 10.4153/CJM-1997-015-x | MR 1447493 | Zbl 0886.05013
[16] D. Merlini, R. Sprugnoli: Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern. Theor. Comput. Sci. 412 (2011), 2988-3001. DOI 10.1016/j.tcs.2010.07.019 | MR 2830262 | Zbl 1220.68079
[17] H. Niederhausen: Inverses of Motzkin and Schröder paths. Integers 12 (2012), Article ID A49, 19 pages. MR 3083422 | Zbl 1290.05011
[18] A. Nkwanta, L. W. Shapiro: Pell walks and Riordan matrices. Fibonacci Q. 43 (2005), 170-180. MR 2147953 | Zbl 1074.60053
[19] E. Pergola, R. A. Sulanke: Schröder triangles, paths, and parallelogram polyominoes. J. Integer Seq. 1 (1998), Article 98.1.7. MR 1677075 | Zbl 0974.05003
[20] J. L. Ramírez, V. F. Sirvent: Generalized Schröder matrix and its combinatorial interpretation. Linear Multilinear Algebra 66 (2018), 418-433. DOI 10.1080/03081087.2017.1301360 | MR 3750599 | Zbl 1387.15004
[21] D. G. Rogers: A Schröder triangle: Three combinatorial problems. Combinatorial Mathematics, V. Lecture Notes in Mathematics 622, Springer, Berlin (1977), 175-196. DOI 10.1007/BFb0069192 | MR 0462964 | Zbl 0368.05004
[22] D. G. Rogers, L. W. Shapiro: Some correspondence involving the Schröder numbers and relations. Combinatorial Mathematics. Lecture Notes in Mathematics 686, Springer, Berlin (1978). DOI 10.1007/BFb0062541 | MR 0526754
[23] E. Schröder: Vier kombinatorische probleme. Schloemilch Z. (Zs. f. Math. u. Phys.) 15 (1870), 361-376. (In German.) JFM 02.0108.04
[24] L. W. Shapiro, S. Getu, W.-J. Woan, L. C. Woodson: The Riordan group. Discrete Appl. Math. 34 (1991), 229-239. DOI 10.1016/0166-218X(91)90088-E | MR 1137996 | Zbl 0754.05010
[25] N. J. A. Sloane: On-line Encyclopedia of Integer Sequences (OEIS) (2018). Available at https://oeis.org.
[26] C. Song: The generalized Schröder theory. Electron. J. Comb. 12 (2005), Article ID 53, 10 pages. MR 2176529 | Zbl 1077.05010
[27] R. Sprugnoli: Riordan arrays and combinatorial sums. Discrete Math. 132 (1994), 267-290. DOI 10.1016/0012-365X(92)00570-H | MR 1297386 | Zbl 0814.05003
[28] R. P. Stanley: Hipparchus, Plutarch, Schröder, and Hough. Am. Math. Mon. 104 (1997), 344-350. DOI 10.2307/2974582 | MR 1450667 | Zbl 0873.01002
[29] R. P. Stanley: Enumerative Combinatorics. Volume 2. Cambridge Studies in Advanced Mathematics 62, Cambridge University Press, Cambridge (1999). DOI 10.1017/CBO9780511609589 | MR 1676282 | Zbl 0928.05001
[30] R. A. Sulanke: Bijective recurrences concerning Schröder paths. Electron. J. Combin. 5 (1998), Article ID R47, 11 pages. MR 1661185 | Zbl 0913.05007
[31] W.-J. Woan: A relation between restricted and unrestricted weighted Motzkin paths. J. Integer Seq. 9 (2006), Article 06.1.7, 12 pages. MR 2188940 | Zbl 1101.05008
[32] S.-L. Yang, Y.-N. Dong, T.-X. He: Some matrix identities on colored Motzkin paths. Discrete Math. 340 (2017), 3081-3091. DOI 10.1016/j.disc.2017.07.006 | MR 3698097 | Zbl 1370.05114
[33] S.-L. Yang, Y.-N. Dong, L. Yang, J. Yin: Half of a Riordan array and restricted lattice paths. Linear Algebra Appl. 537 (2018), 1-11. DOI 10.1016/j.laa.2017.09.027 | MR 3716232 | Zbl 1373.05007
[34] S.-L. Yang, Y.-X. Xu, T.-X. He: $(m,r)$-central Riordan arrays and their applications. Czech. Math. J. 67 (2017), 919-936. DOI 10.21136/CMJ.2017.0165-16 | MR 3736009 | Zbl 06819563
[35] S.-L. Yang, S.-N. Zheng, S.-P. Yuan, T.-X. He: Schröder matrix as inverse of Delannoy matrix. Linear Algebra Appl. 439 (2013), 3605-3614. DOI 10.1016/j.laa.2013.09.044 | MR 3119875 | Zbl 1283.15098

Affiliations:   Lin Yang, Sheng-Liang Yang (corresponding author), Department of Applied Mathematics, Lanzhou University of Technology, Lanzhou, 730050, Gansu, P. R. China, e-mail: yanglimath@163.com, slyang@lut.cn; Tian-Xiao He, Department of Mathematics, Illinois Wesleyan University, Bloomington, IL, 61702-2900, USA, e-mail: the@iwu.edu


 
PDF available at: