PL EN


Preferencje help
Widoczny [Schowaj] Abstrakt
Liczba wyników
Czasopismo
2011 | 9 | 5 | 1121-1134
Tytuł artykułu

Pattern avoiding partitions and Motzkin left factors

Treść / Zawartość
Warianty tytułu
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.
Wydawca
Czasopismo
Rocznik
Tom
9
Numer
5
Strony
1121-1134
Opis fizyczny
Daty
wydano
2011-10-01
online
2011-07-26
Twórcy
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
Typ dokumentu
Bibliografia
Identyfikatory
Identyfikator YADDA
bwmeta1.element.doi-10_2478_s11533-011-0057-4
JavaScript jest wyłączony w Twojej przeglądarce internetowej. Włącz go, a następnie odśwież stronę, aby móc w pełni z niej korzystać.