Generalized Schröder matrices arising from enumeration of lattice paths

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

Czechoslovak Mathematical Journal, Tome 70 (2020) no. 2, pp. 411-433

Abstract (VO)

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.

Détail

DOI : 10.21136/CMJ.2019.0348-18

Classification : 05A15, 05A19, 11B83, 15A24
Keywords: Riordan array; lattice path; Delannoy matrix; Schröder number; Schröder matrix

Bibliographie

[1] Aigner, M.: Enumeration via ballot numbers. Discrete Math. 308 (2008), 2544-2563. | DOI | MR | JFM

[2] Barry, P.: On the central coefficients of Riordan matrices. J. Integer Seq. 16 (2013), Article 13.5.1, 12 pages. | MR | JFM

[3] Bonin, J., Shapiro, L., Simion, R.: Some $q$-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths. J. Stat. Plann. Inference 34 (1993), 35-55. | DOI | MR | JFM

[4] Chen, X., Liang, H., Wang, Y.: Total positivity of Riordan arrays. Eur. J. Comb. 46 (2015), 68-74. | DOI | MR | JFM

[5] Cheon, G.-S., Kim, H., Shapiro, L. W.: Combinatorics of Riordan arrays with identical $A$ and $Z$ sequences. Discrete Math. 312 (2012), 2040-2049. | DOI | MR | JFM

[6] Comtet, L.: Advanced Combinatorics: The Art of Finite and Infinite Expansions. D. Reidel Publishing, Dordrecht (1974). | DOI | MR | JFM

[7] Deutsch, E.: A bijective proof of the equation linking the Schröder numbers, large and small. Discrete Math. 241 (2001), 235-240. | DOI | MR | JFM

[8] Deutsch, E., Munarini, E., Rinaldi, S.: Skew Dyck paths. J. Stat. Plann. Inference 140 (2010), 2191-2203. | DOI | MR | JFM

[9] Dziemiańczuk, M.: Counting lattice paths with four types of steps. Graphs Comb. 30 (2014), 1427-1452. | DOI | MR | JFM

[10] He, T.-X.: Parametric Catalan numbers and Catalan triangles. Linear Algebra Appl. 438 (2013), 1467-1484. | DOI | MR | JFM

[11] Humphreys, K.: A history and a survey of lattice path enumeration. J. Stat. Plann. Inference 140 (2010), 2237-2254. | DOI | MR | JFM

[12] Luzón, A., Merlini, D., Morón, M., Sprugnoli, R.: Identities induced by Riordan arrays. Linear Algebra Appl. 436 (2011), 631-647. | DOI | MR | JFM

[13] Mansour, T., Schork, M., Sun, Y.: Motzkin numbers of higher ranks: Generating function and explicit expression. J. Integer Seq. 10 (2007), Article 07.7.4, 11 pages. | MR | JFM

[14] Merlini, D.: Proper generating trees and their internal path length. Discrete Appl. Math. 156 (2008), 627-646. | DOI | MR | JFM

[15] Merlini, D., Rogers, D. G., Sprugnoli, R., Verri, M. C.: On some alternative characterizations of Riordan arrays. Can. J. Math. 49 (1997), 301-320. | DOI | MR | JFM

[16] Merlini, D., Sprugnoli, R.: Algebraic aspects of some Riordan arrays related to binary words avoiding a pattern. Theor. Comput. Sci. 412 (2011), 2988-3001. | DOI | MR | JFM

[17] Niederhausen, H.: Inverses of Motzkin and Schröder paths. Integers 12 (2012), Article ID A49, 19 pages. | MR | JFM

[18] Nkwanta, A., Shapiro, L. W.: Pell walks and Riordan matrices. Fibonacci Q. 43 (2005), 170-180. | MR | JFM

[19] Pergola, E., Sulanke, R. A.: Schröder triangles, paths, and parallelogram polyominoes. J. Integer Seq. 1 (1998), Article 98.1.7. | MR | JFM

[20] Ramírez, J. L., Sirvent, V. F.: Generalized Schröder matrix and its combinatorial interpretation. Linear Multilinear Algebra 66 (2018), 418-433. | DOI | MR | JFM

[21] Rogers, D. G.: A Schröder triangle: Three combinatorial problems. Combinatorial Mathematics, V Lecture Notes in Mathematics 622, Springer, Berlin (1977), 175-196. | DOI | MR | JFM

[22] Rogers, D. G., Shapiro, L. W.: Some correspondence involving the Schröder numbers and relations. Combinatorial Mathematics Lecture Notes in Mathematics 686, Springer, Berlin (1978). | DOI | MR

[23] Schröder, E.: Vier kombinatorische probleme. Schloemilch Z. (Zs. f. Math. u. Phys.) 15 (1870), 361-376 German \99999JFM99999 02.0108.04.

[24] Shapiro, L. W., Getu, S., Woan, W.-J., Woodson, L. C.: The Riordan group. Discrete Appl. Math. 34 (1991), 229-239. | DOI | MR | JFM

[25] Sloane, N. J. A.: On-line Encyclopedia of Integer Sequences (OEIS). Available at https://oeis.org (2018). | MR

[26] Song, C.: The generalized Schröder theory. Electron. J. Comb. 12 (2005), Article ID 53, 10 pages. | MR | JFM

[27] Sprugnoli, R.: Riordan arrays and combinatorial sums. Discrete Math. 132 (1994), 267-290. | DOI | MR | JFM

[28] Stanley, R. P.: Hipparchus, Plutarch, Schröder, and Hough. Am. Math. Mon. 104 (1997), 344-350. | DOI | MR | JFM

[29] Stanley, R. P.: Enumerative Combinatorics. Volume 2. Cambridge Studies in Advanced Mathematics 62, Cambridge University Press, Cambridge (1999). | DOI | MR | JFM

[30] Sulanke, R. A.: Bijective recurrences concerning Schröder paths. Electron. J. Combin. 5 (1998), Article ID R47, 11 pages. | DOI | MR | JFM

[31] Woan, W.-J.: A relation between restricted and unrestricted weighted Motzkin paths. J. Integer Seq. 9 (2006), Article 06.1.7, 12 pages. | MR | JFM

[32] Yang, S.-L., Dong, Y.-N., He, T.-X.: Some matrix identities on colored Motzkin paths. Discrete Math. 340 (2017), 3081-3091. | DOI | MR | JFM

[33] Yang, S.-L., Dong, Y.-N., Yang, L., Yin, J.: Half of a Riordan array and restricted lattice paths. Linear Algebra Appl. 537 (2018), 1-11. | DOI | MR | JFM

[34] Yang, S.-L., Xu, Y.-X., He, T.-X.: $(m,r)$-central Riordan arrays and their applications. Czech. Math. J. 67 (2017), 919-936. | DOI | MR | JFM

[35] Yang, S.-L., Zheng, S.-N., Yuan, S.-P., He, T.-X.: Schröder matrix as inverse of Delannoy matrix. Linear Algebra Appl. 439 (2013), 3605-3614. | DOI | MR | JFM