Pattern avoiding partitions and Motzkin left factors

Toufik Mansour; Mark Shattuck

Open Mathematics (2011)

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

Abstract

top
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.

How to cite

top

Toufik 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. [1] Alonso L., Schott R., Random Generation of Trees, Kluwer, Dordrecht, Boston, 1995 
  2. [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. [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. [4] Benjamin AT., Quinn J.J., Proofs that Really Count, Dolciani Math. Exp., 27, Mathematical Association of America, Washington, 2003 
  5. [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. [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. [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. [8] Jelínek V, Mansour T., On pattern avoiding partitions, Electron. J. Combin., 2008, 15(1), #R39 Zbl1179.05014
  9. [9] Josuat-Vergès M., Rubey M., Crossings, Motzkin paths and moments, preprint available at http://arxiv.org/abs/1008.3093 
  10. [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. [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. [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. [13] Sagan B.E., Pattern avoidance in set partitions, Ars Combin., 2010, 94(1), 79–96 Zbl1240.05018
  14. [14] Sapounakis A., Tsikouras P., Counting peaks and valleys in k-colored Motzkin paths, Electron. J. Combin., 2005, 12, #R16 Zbl1060.05009
  15. [15] Simion R., Schmidt F.W., Restricted permutations, European J. Combin., 1985, 6(4), 383–406 Zbl0615.05002
  16. [16] Sloane N.J.A., The On-Line Encyclopedia of Integer Sequences, http://oeis.org Zbl1274.11001

NotesEmbed ?

top

You must be logged in to post comments.

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

Only the controls for the widget will be shown in your chosen language. Notes will be shown in their authored language.

Tells the widget how many notes to show per page. You can cycle through additional notes using the next and previous controls.

    
                

                
Note: Best practice suggests putting the JavaScript code just before the closing </body> tag.