A relation between Schröder paths and Motzkin paths. (English) Zbl 1458.05021
Summary: A small \(q\)-Schröder path of semilength \(n\) is a lattice path from (0, 0) to \((2n, 0)\) using up steps \(U = (1, 1)\), horizontal steps \(H = (2, 0)\), and down steps \(D = (1,-1)\) such that it stays weakly above the x-axis, has no horizontal steps on the \(x\)-axis, and each horizontal step comes in \(q\) colors. In this paper, we provide a bijection between the set of small \(q\)-Schröder paths of semilength \(n+1\) and the set of \((q+2, q+1)\)-Motzkin paths of length \(n\). Furthermore, a one-to-one correspondence between the set of small 3-Schröder paths of semilength \(n\) and the set of Catalan rook paths of semilength \(n\) is obtained, and a bijection between small 4-Schröder paths and Catalan queen paths is also presented.
MSC:
| 05A15 | Exact enumeration problems, generating functions |
| 05A05 | Permutations, words, matrices |
| 15A09 | Theory of matrix inversion and generalized inverses |
Keywords:
Schröder path; Motzkin path; Catalan rook path; Catalan queen path; \(q\)-Schröder numbers; \((a, b)\)-Motzkin numbersSoftware:
OEISOnline Encyclopedia of Integer Sequences:
Table T(n,k), n>=0 and k>=0, read by antidiagonals: the k-th column given by the k-th Narayana polynomial.Square array read by ascending antidiagonals, n>=0, k>=0. Row n is the expansion of (1-n*x-sqrt(n^2*x^2-2*n*x-4*x+1))/(2*x).
References:
| [1] | Barcucci, E.; Lungo, A.; Pergola, E.; Pinzani, R., ECO: a methodology for the enumeration of combinatorial objects, J. Differ. Equ. Appl., 5, 435-490 (1999) · Zbl 0944.05005 · doi:10.1080/10236199908808200 |
| [2] | Barcucci, E.; Lungo, A.; Pergola, E.; Pinzani, R., Some combinatorial interpretations of \(q\)-analogs of Schröder numbers, Ann. Combin., 3, 171-190 (1999) · Zbl 0934.05008 · doi:10.1007/BF01608782 |
| [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., 34, 35-55 (1993) · Zbl 0783.05008 · doi:10.1016/0378-3758(93)90032-2 |
| [4] | Chen, Z.; Pan, H., Identities involving weighted Catalan, Schröder and Motzkin paths, Adv. Appl. Math., 86, 81-98 (2017) · Zbl 1358.05013 · doi:10.1016/j.aam.2016.11.011 |
| [5] | Chen, C.; Wang, C., Noncrossing linked partitions and large \((3, 2)\)-Motzkin paths, Discrete Math., 312, 1918-1922 (2012) · Zbl 1243.05017 · doi:10.1016/j.disc.2012.02.017 |
| [6] | Chen, C.; Yan, F.; Yang, M., Identities from weighted Motzkin paths, Adv. Appl. Math., 41, 329-334 (2008) · Zbl 1148.05007 · doi:10.1016/j.aam.2004.11.007 |
| [7] | Coker, C., Enumerating a class of lattice paths, Discrete Math., 271, 13-28 (2003) · Zbl 1027.05002 · doi:10.1016/S0012-365X(03)00037-2 |
| [8] | Comtet, L., Advanced Combinatorics (1974), Boston: D. Reidel Publishing Company, Boston · Zbl 0283.05001 |
| [9] | Deng, E.; Yan, W., Some identities on the Catanlan, Motzkin and Schröder numbers, Discrete Appl. Math., 156, 2781-2789 (2008) · Zbl 1148.05011 · doi:10.1016/j.dam.2007.11.014 |
| [10] | Deutsch, E., An involution on Dyck paths and its consequences, Discrete Math., 204, 163-166 (1999) · Zbl 0932.05005 · doi:10.1016/S0012-365X(98)00370-7 |
| [11] | Deutsch, E., Dyck path enumeration, Discrete Math., 204, 167-202 (1999) · Zbl 0932.05006 · doi:10.1016/S0012-365X(98)00371-9 |
| [12] | Deutsch, E.; Munarini, E.; Rinaldi, S., Skew Dyck paths, J. Stat. Plann. Inference, 140, 2191-2203 (2010) · Zbl 1232.05010 · doi:10.1016/j.jspi.2010.01.015 |
| [13] | Deutsch, E.; Shapiro, L., A bijection between ordered trees and \(2\)-Motzkin paths and its many consequences, Discrete Math., 256, 655-6700 (2002) · Zbl 1012.05050 · doi:10.1016/S0012-365X(02)00341-2 |
| [14] | Dutour, I.; Fédou, JM, Object grammars and bijections, Theor. Comput. Sci., 290, 1915-1929 (2003) · Zbl 1044.68075 · doi:10.1016/S0304-3975(02)00368-7 |
| [15] | Dziemiańczuk, M., Counting lattice paths with four types of steps, Graphs Combin., 30, 1427-1452 (2014) · Zbl 1306.05007 · doi:10.1007/s00373-013-1357-1 |
| [16] | Flajolet, P.; Sedgewick, R., Analytic Combinatorics (2009), Cambridge: Cambridge University Press, Cambridge · Zbl 1165.05001 |
| [17] | Foata, D.; Zeilberger, D., A classic proof of a recurrence for a very classical sequence, J. Combin. Theory Ser. A, 80, 380-384 (1997) · Zbl 0883.05007 · doi:10.1006/jcta.1997.2814 |
| [18] | Gessel, IM, Lagrange inversion, J. Combin. Theory Ser. A, 144, 2, 212-249 (2016) · Zbl 1343.05021 · doi:10.1016/j.jcta.2016.06.018 |
| [19] | Hennessy, A., Bijection of Motzkin paths using Riordan decompositions, Graphs Combin., 35, 169-187 (2019) · Zbl 1407.05134 · doi:10.1007/s00373-018-1982-9 |
| [20] | Huh, J.S., Park, S.K.: Generalized small Schröder numbers. Electron. J. Combin. 22(3), #P3.14 (2015) · Zbl 1327.05017 |
| [21] | Humphreys, K., A history and a survey of lattice path enumeration, J. Stat. Plann., 140, 8, 2237-2254 (2010) · Zbl 1204.05015 · doi:10.1016/j.jspi.2010.01.020 |
| [22] | Kung, JPS; Mier, A., Catalan lattice paths with rook, bishop and spider steps, J. Combin. Theory Ser. A, 120, 2, 379-389 (2013) · Zbl 1256.05008 · doi:10.1016/j.jcta.2012.08.010 |
| [23] | Mohanty, SG, Lattice Path Counting and Applications (1979), New York: Academic Press, New York · Zbl 0455.60013 |
| [24] | Narayana, TV, Lattice Path Combinatorics with Statistical Applications (1979), Toronto: University of Toronto Press, Toronto · Zbl 0437.05001 |
| [25] | Shapiro, L.W., Wang C.J.: A bijection between \(3\)-Motzkin baths and Schröder baths with no peak at odd height. J. Integer Seq. 12, Article 09.3.2 (2009) · Zbl 1165.05300 |
| [26] | Sloane, N.J.A.: The On-line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org (2020) · Zbl 1044.11108 |
| [27] | Song, C.: The generalized Schröder theory. Electron. J. Combin. 12, #R53 (2005) · Zbl 1077.05010 |
| [28] | Stanley, RP, Enumerative Combinatorics (1999), Cambridge: Cambridge University Press, Cambridge · Zbl 0928.05001 |
| [29] | Sulanke, RA, The Narayana distribution, J. Stat. Plann. Inference, 101, 311-326 (2002) · Zbl 1001.05009 · doi:10.1016/S0378-3758(01)00192-6 |
| [30] | Woan, W.: A recurisive relation for weighted Motzkin sequences. J. Integer Seq. 8, Article 05.1.6 (2005) · Zbl 1065.05012 |
| [31] | Woan, W.: A relation between restricted and unrestricted weighted Motzkin paths. J. Integer Seq. 9, Article 06.1.7 (2006) · Zbl 1101.05008 |
| [32] | Yan, S.H.F.: From \((2,3)\)-Motzkin paths to Schröder paths. J. Integer Seq. 10, Article 07.9.1 (2007) · Zbl 1143.05005 |
| [33] | Yan, SHF; Zhang, Y., On lattice paths with four types of steps, Graphs Combin., 31, 1077-1084 (2015) · Zbl 1317.05009 · doi:10.1007/s00373-014-1424-2 |
| [34] | Yang, SL; Zheng, SN; Yuan, SP; He, TX, Schröder matrix as inverse of Delannoy matrix, Linear Algebra Appl., 439, 12, 3605-3614 (2013) · Zbl 1283.15098 · doi:10.1016/j.laa.2013.09.044 |
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.
