Pattern avoiding partitions and Motzkin left factors

• Autorzy: Toufik Mansour , Mark Shattuck
• Języki publikacji: EN

Abstrakty

EN

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.

Słowa kluczowe

EN

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

Kategorie tematyczne

• 05A18: Partitions of sets
• 05A15: Exact enumeration problems, generating functions

• Wydawca: De Gruyter Open
• Czasopismo: Open Mathematics
• Rocznik: 2011
• Tom: 9
• Numer: 5
• Strony: 1121-1134

Daty

wydano

2011-10-01

online

2011-07-26

Twórcy

autor

Toufik Mansour

• University of Haifa

autor

Mark Shattuck

• University of Haifa

Bibliografia

• [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
• [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
• [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
• [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
• [8] Jelínek V, Mansour T., On pattern avoiding partitions, Electron. J. Combin., 2008, 15(1), #R39
• [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
• [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
• [13] Sagan B.E., Pattern avoidance in set partitions, Ars Combin., 2010, 94(1), 79–96
• [14] Sapounakis A., Tsikouras P., Counting peaks and valleys in k-colored Motzkin paths, Electron. J. Combin., 2005, 12, #R16
• [15] Simion R., Schmidt F.W., Restricted permutations, European J. Combin., 1985, 6(4), 383–406
• [16] Sloane N.J.A., The On-Line Encyclopedia of Integer Sequences, http://oeis.org

Identyfikatory

DOI

10.2478/s11533-011-0057-4