Avoidance of Type (1,2) Patterns by Catalan Words

Toufik Mansour^1, and Mark Shattuck²

¹Department of Mathematics, University of Haifa, 31905 Haifa, Israel

²Department of Mathematics, University of Tennessee, Knoxville, TN 37996

Cite this paper:
Toufik Mansour and Mark Shattuck. Avoidance of Type (1,2) Patterns by Catalan Words. Turkish Journal of Analysis and Number Theory. 2017; 5(3):101-116. doi: 10.12691/tjant-5-3-4

Abstract

A certain subset of the multiset permutations of length n satisfying two restrictions has been recently shown to be enumerated by the Catalan number C_n−1. These sequences have been termed Catalan words and are closely related to the 321-avoiding permutations. Here, we consider the problem of avoidance of patterns of type (1,2) wherein the second and third letters within an occurrence of a pattern are required to be adjacent. We derive in several cases functional equations satisfied by the generating functions enumerating members of the avoidance class which we solve by various methods. In one case, the generating function can be expressed in terms of a sum of reciprocals of Chebyshev polynomials, while in another, in terms of a previously studied q-Bell number. Among the sequences arising as enumerators of avoidance classes are the Motzkin and Fibonacci numbers. In several cases, it is more convenient to consider first the problem of avoidance on the subset of Catalan words whose members have no adjacent letters the same before moving to the larger problem on all Catalan words.

Keywords:
vincular patterns functional equation kernel method pattern avoidance

This work is licensed under a Creative Commons Attribution 4.0 International License. To view a copy of this license, visit http://creativecommons.org/licenses/by/4.0/

References:

[1]	L. Alonso and R. Schott, Random Generation of Trees, Kluwer Academic Publishers, Dordrecht, The Netherlands 1995.
[2]	A. Claesson, Generalized pattern avoidance, European J. Combin. 22:7 (2001), 961-971.
[3]	A. Claesson and T. Mansour, Counting occurrences of a pattern of type (1,2) or (2,1) in permutations, Adv. in Appl. Math. 29:2 (2002), 293-310.
[4]	S. Heubach, T. Mansour, and A. O. Munagi, Avoiding permutations of type (2,1) in compositions, Online J. Anal. Comb. 4 (2009), Article 3.
[5]	Q. H. Hou and T. Mansour, Kernel method and systems of functional equations with several conditions, J. Comput.Appl. Math. 235:5 (2011), 1205-1212.
[6]	T. Mansour and M. Shattuck, Avoiding type (1,2) or (2,1) patterns in a partition of a set, Integers 12 (2012), #A20.
[7]	T. Mansour and M. Shattuck, Chebyshev polynomials and statistics on a new collection of words in the Catalan family, J. Difference Equ. Appl. 20:11 (2014), 1568-1582.
[8]	T. Mansour and M. Shattuck, Avoidance of a pattern of length three by Catalan words, Filomat 31:3 (2017), 543-558.
[9]	S. Milne, A q-analogue of restricted growth functions, Dobinski’s equality, and Charlier polynomials, Trans. Amer. Math. Soc. 245 (1978), 89-118.
[10]	T. Rivlin, Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory, John Wiley, New York, 1990.
[11]	N. J. A. Sloane, On-line Encyclopedia of Integer Sequences, http://oeis.org, 2015.
[12]	C. Stump, On a new collection of words in the Catalan family, J. Integer Seq. 17 (2014), Art. 14.7.1.
[13]	C. G. Wagner, Partition statistics and q-Bell numbers (q = −1), J. Integer Seq. 7 (2004), Art. 04.1.1.