# Pattern avoiding partitions and Motzkin left factors

Open Mathematics (2011)

- Volume: 9, Issue: 5, page 1121-1134
- ISSN: 2391-5455

## Access Full Article

top## Abstract

top## How to cite

topToufik Mansour, and Mark Shattuck. "Pattern avoiding partitions and Motzkin left factors." Open Mathematics 9.5 (2011): 1121-1134. <http://eudml.org/doc/269279>.

@article{ToufikMansour2011,

abstract = {Let L n, n ≥ 1, denote the sequence which counts the number of paths from the origin to the line x = n − 1 using (1, 1), (1, −1), and (1, 0) steps that never dip below the x-axis (called Motzkin left factors). The numbers L n count, among other things, certain restricted subsets of permutations and Catalan paths. In this paper, we provide new combinatorial interpretations for these numbers in terms of finite set partitions. In particular, we identify four classes of the partitions of size n, all of which have cardinality L n and each avoiding a set of two classical patterns of length four. We obtain a further generalization in one of the cases by considering a pair of statistics on the partition class. In a couple of cases, to show the result, we make use of the kernel method to solve a functional equation arising after a certain parameter has been introduced.},

author = {Toufik Mansour, Mark Shattuck},

journal = {Open Mathematics},

keywords = {Pattern avoidance; Motzkin number; Motzkin left factor; q-generalization; -generalization},

language = {eng},

number = {5},

pages = {1121-1134},

title = {Pattern avoiding partitions and Motzkin left factors},

url = {http://eudml.org/doc/269279},

volume = {9},

year = {2011},

}

TY - JOUR

AU - Toufik Mansour

AU - Mark Shattuck

TI - Pattern avoiding partitions and Motzkin left factors

JO - Open Mathematics

PY - 2011

VL - 9

IS - 5

SP - 1121

EP - 1134

AB - Let L n, n ≥ 1, denote the sequence which counts the number of paths from the origin to the line x = n − 1 using (1, 1), (1, −1), and (1, 0) steps that never dip below the x-axis (called Motzkin left factors). The numbers L n count, among other things, certain restricted subsets of permutations and Catalan paths. In this paper, we provide new combinatorial interpretations for these numbers in terms of finite set partitions. In particular, we identify four classes of the partitions of size n, all of which have cardinality L n and each avoiding a set of two classical patterns of length four. We obtain a further generalization in one of the cases by considering a pair of statistics on the partition class. In a couple of cases, to show the result, we make use of the kernel method to solve a functional equation arising after a certain parameter has been introduced.

LA - eng

KW - Pattern avoidance; Motzkin number; Motzkin left factor; q-generalization; -generalization

UR - http://eudml.org/doc/269279

ER -

## References

top- [1] Alonso L., Schott R., Random Generation of Trees, Kluwer, Dordrecht, Boston, 1995
- [2] Banderier C., Bousquet-Mélou M., Denise A., Flajolet P., Gardy D., Gouyou-Beauchamps D., Generating functions for generating trees, Discrete Math., 2002, 246(1–3), 29–55 http://dx.doi.org/10.1016/S0012-365X(01)00250-3 Zbl0997.05007
- [3] Barcucci E., Del Lungo A., Pergola E., Pinzani R., From Motzkin to Catalan permutations, Discrete Math., 2000, 217(1–3), 33–49 http://dx.doi.org/10.1016/S0012-365X(99)00254-X Zbl0965.05004
- [4] Benjamin AT., Quinn J.J., Proofs that Really Count, Dolciani Math. Exp., 27, Mathematical Association of America, Washington, 2003
- [5] Flajolet P., Combinatorial aspects of continued fractions, Discrete Math., 1980, 32(2), 125–161 http://dx.doi.org/10.1016/0012-365X(80)90050-3
- [6] Gouyou-Beauchamps D., Viennot G., Equivalence of the two-dimensional directed animal problem to a one-dimensional path problem, Adv. in Appl. Math., 1988, 9(3), 334–357 http://dx.doi.org/10.1016/0196-8858(88)90017-6 Zbl0727.05036
- [7] Goyt A.M., Avoidance of partitions of a three-element set, Adv. in Appl. Math., 2008, 41(1), 95–114 http://dx.doi.org/10.1016/j.aam.2006.07.006 Zbl1139.05003
- [8] Jelínek V, Mansour T., On pattern avoiding partitions, Electron. J. Combin., 2008, 15(1), #R39 Zbl1179.05014
- [9] Josuat-Vergès M., Rubey M., Crossings, Motzkin paths and moments, preprint available at http://arxiv.org/abs/1008.3093
- [10] Klazar M., On abab-free and abba-free set partitions, European J. Combin., 1996, 17(1), 53–68 http://dx.doi.org/10.1006/eujc.1996.0005
- [11] Knuth D.E., The Art of Computer Programming, Vol. 1,3, Addison-Wesley Series in Computer Science and Information Processing, Addison-Wesley, Reading, 1968, 1974 Zbl0191.17903
- [12] Milne S.C., A g-analog of restricted growth functions, Dobinski’s equality, and Charlier polynomials, Trans. Amer. Math. Soc, 1978, 245, 89–118 Zbl0402.05007
- [13] Sagan B.E., Pattern avoidance in set partitions, Ars Combin., 2010, 94(1), 79–96 Zbl1240.05018
- [14] Sapounakis A., Tsikouras P., Counting peaks and valleys in k-colored Motzkin paths, Electron. J. Combin., 2005, 12, #R16 Zbl1060.05009
- [15] Simion R., Schmidt F.W., Restricted permutations, European J. Combin., 1985, 6(4), 383–406 Zbl0615.05002
- [16] Sloane N.J.A., The On-Line Encyclopedia of Integer Sequences, http://oeis.org Zbl1274.11001

## NotesEmbed ?

topTo embed these notes on your page include the following JavaScript code on your page where you want the notes to appear.