Abstract
This paper concentrates on the set \(\mathcal {V}_n\) of weighted Dyck paths of length 2n with special restrictions on the level of valleys. We first give its explicit formula of the counting generating function in terms of certain weight functions. When the weight functions are specialized, some connections are builded between \(\mathcal {V}_n\) and other classical combinatorial structures such as (a, b)-Motzkin paths, q-Schröder paths, Delannoy paths and complete k-ary trees. Some bijections are also established between these settings and \(\mathcal {V}_n\) subject to certain special weight functions.
This is a preview of subscription content, log in via an institution to check access.
Similar content being viewed by others
References
Banderier, C., Schwer, S.: Why Delannoy numbers? J. Stat. Plann. Inference 135, 40–54 (2005)
Barcucci, E., Del Lungo, A., Fezzi, A., Pinzani, R.: Nondecreasing Dyck paths and \(q\)-Fibonacci numbers. Discrete Math. 170, 211–217 (1997)
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, 35–55 (1993)
Comtet, L.: Advanced Combinatorics, D. Reidel Publishing Company, Dordrecht-Holland (1974)
Czabarka, E., Flórez, R., Junes, L.: Some enumerations on non-decreasing Dyck paths. Electron. J. Combin. 22, 1–22 (2015). ((p1.3))
Czabarka, E., Flórez, R., Junes, L., Ramírez, J.: Enumerations of peaks and valleys on non-decreasing Dyck paths. Discrete Math. 341, 2789–2807 (2018)
Deutsch, E., Prodinger, H.: A bijection between directed column-convex polyominoes and ordered trees of height at most three. Theor. Comput. Sci. 307, 319–325 (2003)
Deutsch, E.: Dyck path enumeration. Discrete Math. 204, 167–202 (1999)
Flórez, R., Junes, L., Ramírez, J.: Enumerating several aspects of non-decreasing Dyck paths. Discrete Math. 342, 3079–3097 (2019)
Flórez, R., Ramírez, J.: Some enumerations on non-decreasing Motzkin paths. Australas. J. Combin. 72(1), 138–154 (2018)
Flórez, R., Ramírez, J.: Enumerations of t-Dyck paths with non-decreasing valleys, 2019 (submitted for publication)
Prodinger, H.: Words, Dyck paths, trees, and bijections. In: Words, Semigroups, and Transductions, pp. 369–379. World Scientific (2001)
Gessel, I.M.: Lagrange inversion. J. Combin. Theory Ser. A 144, 212–249 (2016)
Stanley, R.P.: Catalan addendum. http://www-math.mit.edu/rstan/ec/catadd.pdf a version of 25 May 2013
Stanley, R.P.: Enumberative Combinatorics, vol. 2. Cambridge University Press, Cambridge (1999)
Woan,W.-J.: A recursive relation for weighted Motzkin sequences. J. Integer Seq. 8, Article 05.1.6 (2005)
Yang, L., Yang, S.-L.: A relation between Schröder paths and Motzkin paths. Graphs Combin. 36, 1489–1502 (2020)
Acknowledgements
The authors are grateful to the referees for the helpful suggestions and comments. The Project is sponsored by “Liaoning BaiQianWan Talents Program”and by the Fundamental Research Funds for the Central Universities Under Contract.
Author information
Authors and Affiliations
Corresponding author
Ethics declarations
Conflict of interest
The authors declare that they have no known competing financial interests or personal relationships that could have appeared to influence the work reported in this paper.
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
Sun, Y., Liu, Q. & Liu, Y. Weighted Dyck Paths with Special Restrictions on the Levels of Valleys. Graphs and Combinatorics 38, 48 (2022). https://doi.org/10.1007/s00373-021-02451-1
Received:
Revised:
Accepted:
Published:
DOI: https://doi.org/10.1007/s00373-021-02451-1