Identities involving weighted Catalan, Schröder and Motzkin paths. (English) Zbl 1358.05013
Summary: In this paper, we investigate the weighted Catalan, Motzkin and Schröder numbers together with the corresponding weighted paths. The relation between these numbers is illustrated by three equations, which also lead to some known and new interesting identities. To show these three equations, we provide combinatorial proofs. One byproduct is to find a bijection between two sets of Catalan paths: one consisting of those with \(k\) valleys, and the other consisting of \(kN\) steps in even positions.
MSC:
05A15 | Exact enumeration problems, generating functions |
05A10 | Factorials, binomial coefficients, combinatorial functions |
05A19 | Combinatorial identities, bijective combinatorics |
Keywords:
Motzkin numbers; Catalan numbers; Narayana numbers; Schröder numbers; weighted lattice paths; bijectionReferences:
[1] | Bonin, J.; Shapiro, L.; Simion, R., Some \(q\)-analogues of the Schröder numbers arising from combinatorial statistics on lattice paths, J. Statist. Plann. Inference, 34, 35-55 (1993) · Zbl 0783.05008 |
[2] | Chen, William Y. C.; Wang, Carol J., Noncrossing linked partitions and large \((3, 2)\)-Motzkin paths, Discrete Math., 312, 1918-1922 (2012) · Zbl 1243.05017 |
[3] | Chen, William Y. C.; Yan, Sherry H. F.; Yang, Laura L. M., Identities from weighted Motzkin paths, Adv. in Appl. Math., 41, 329-334 (2008) · Zbl 1148.05007 |
[4] | Coker, C., Enumerating a class of lattice paths, Discrete Math., 271, 13-28 (2003) · Zbl 1027.05002 |
[5] | Delest, M.; Viennot, G., Algebraic languages and polyominoes enumeration, Theoret. Comput. Sci., 34, 169-206 (1984) · Zbl 0985.68516 |
[6] | Donaghey, R.; Shapiro, L., Motzkin numbers, J. Combin. Theory Ser. A, 23, 291-301 (1977) · Zbl 0417.05007 |
[7] | Petersen, T. K., Eulerian Numbers (2015), Birkhäuser/Springer: Birkhäuser/Springer New York · Zbl 1337.05001 |
[8] | Stanley, R. P., Enumerative Combinatorics, vol. 2 (1999), Cambridge University Press: Cambridge University Press Cambridge · Zbl 0928.05001 |
[9] | Stanley, R. P., Catalan Numbers (2015), Cambridge University Press: Cambridge University Press Cambridge · Zbl 1317.05010 |
[10] | Yan, S. H.F., From (2, 3)-Motzkin paths to Schröder paths, J. Integer Seq., 10, Article 07.9.1 pp. (2007) · Zbl 1143.05005 |
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.