Abstract
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.
Similar content being viewed by others
References
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)
Barcucci, E., Lungo, A., Pergola, E., Pinzani, R.: Some combinatorial interpretations of \(q\)-analogs of Schröder numbers. Ann. Combin. 3, 171–190 (1999)
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)
Chen, Z., Pan, H.: Identities involving weighted Catalan, Schröder and Motzkin paths. Adv. Appl. Math. 86, 81–98 (2017)
Chen, C., Wang, C.: Noncrossing linked partitions and large \((3, 2)\)-Motzkin paths. Discrete Math. 312, 1918–1922 (2012)
Chen, C., Yan, F., Yang, M.: Identities from weighted Motzkin paths. Adv. Appl. Math. 41, 329–334 (2008)
Coker, C.: Enumerating a class of lattice paths. Discrete Math. 271, 13–28 (2003)
Comtet, L.: Advanced Combinatorics. D. Reidel Publishing Company, Boston (1974)
Deng, E., Yan, W.: Some identities on the Catanlan, Motzkin and Schröder numbers. Discrete Appl. Math. 156, 2781–2789 (2008)
Deutsch, E.: An involution on Dyck paths and its consequences. Discrete Math. 204, 163–166 (1999)
Deutsch, E.: Dyck path enumeration. Discrete Math. 204, 167–202 (1999)
Deutsch, E., Munarini, E., Rinaldi, S.: Skew Dyck paths. J. Stat. Plann. Inference 140, 2191–2203 (2010)
Deutsch, E., Shapiro, L.: A bijection between ordered trees and \(2\)-Motzkin paths and its many consequences. Discrete Math. 256, 655–6700 (2002)
Dutour, I., Fédou, J.M.: Object grammars and bijections. Theor. Comput. Sci. 290, 1915–1929 (2003)
Dziemiańczuk, M.: Counting lattice paths with four types of steps. Graphs Combin. 30, 1427–1452 (2014)
Flajolet, P., Sedgewick, R.: Analytic Combinatorics. Cambridge University Press, Cambridge (2009)
Foata, D., Zeilberger, D.: A classic proof of a recurrence for a very classical sequence. J. Combin. Theory Ser. A 80, 380–384 (1997)
Gessel, I.M.: Lagrange inversion. J. Combin. Theory Ser. A 144(2), 212–249 (2016)
Hennessy, A.: Bijection of Motzkin paths using Riordan decompositions. Graphs Combin. 35, 169–187 (2019)
Huh, J.S., Park, S.K.: Generalized small Schröder numbers. Electron. J. Combin. 22(3), #P3.14 (2015)
Humphreys, K.: A history and a survey of lattice path enumeration. J. Stat. Plann. 140(8), 2237–2254 (2010)
Kung, J.P.S., Mier, A.: Catalan lattice paths with rook, bishop and spider steps. J. Combin. Theory Ser. A 120(2), 379–389 (2013)
Mohanty, S.G.: Lattice Path Counting and Applications. Academic Press, New York (1979)
Narayana, T.V.: Lattice Path Combinatorics with Statistical Applications. University of Toronto Press, Toronto (1979)
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)
Sloane, N.J.A.: The On-line Encyclopedia of Integer Sequences. Published electronically at http://oeis.org (2020)
Song, C.: The generalized Schröder theory. Electron. J. Combin. 12, #R53 (2005)
Stanley, R.P.: Enumerative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)
Sulanke, R.A.: The Narayana distribution. J. Stat. Plann. Inference 101, 311–326 (2002)
Woan, W.: A recurisive relation for weighted Motzkin sequences. J. Integer Seq. 8, Article 05.1.6 (2005)
Woan, W.: A relation between restricted and unrestricted weighted Motzkin paths. J. Integer Seq. 9, Article 06.1.7 (2006)
Yan, S.H.F.: From \((2,3)\)-Motzkin paths to Schröder paths. J. Integer Seq. 10, Article 07.9.1 (2007)
Yan, S.H.F., Zhang, Y.: On lattice paths with four types of steps. Graphs Combin. 31, 1077–1084 (2015)
Yang, S.L., Zheng, S.N., Yuan, S.P., He, T.X.: Schröder matrix as inverse of Delannoy matrix. Linear Algebra Appl. 439(12), 3605–3614 (2013)
Acknowledgements
The authors would like to thank the referees for their helpful suggestions. This work is supported by the National Natural Science Foundation of China (Grant Nos. 11861045, 11561044) and the Hongliu Foundation of First-class Disciplines of Lanzhou University of Technology, China.
Author information
Authors and Affiliations
Corresponding author
Additional information
Publisher's Note
Springer Nature remains neutral with regard to jurisdictional claims in published maps and institutional affiliations.
Rights and permissions
About this article
Cite this article
Yang, L., Yang, SL. A Relation Between Schröder Paths and Motzkin Paths. Graphs and Combinatorics 36, 1489–1502 (2020). https://doi.org/10.1007/s00373-020-02185-6
Received:
Revised:
Published:
Issue Date:
DOI: https://doi.org/10.1007/s00373-020-02185-6
Keywords
- Schröder path
- Motzkin path
- Catalan rook path
- Catalan queen path
- q-Schröder numbers
- (a, b)-Motzkin numbers