Simultaneous avoidance of generalized patterns

Sergey Kitaev, Toufik Mansour

Research output: Contribution to journalArticle

7 Citations (Scopus)

Abstract

In [BabStein] Babson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. In [Kit1] Kitaev considered simultaneous avoidance (multi-avoidance) of two or more 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. There either an explicit or a recursive formula was given for all but one case of simultaneous avoidance of more than two patterns.
In this paper we find the exponential generating function for the remaining case. Also we consider permutations that avoid a pattern of the form x−yz or xy−z and begin with one of the patterns 12...k, k(k−1)...1, 23...k1, (k−1)(k−2)...1k or end with one of the patterns 12...k, k(k−1)...1, 1k(k−1)...2, k12...(k−1). For each of these cases we find either the ordinary or exponential generating functions or a precise formula for the number of such permutations. Besides we generalize some of the obtained results as well as some of the results given in [Kit3]: we consider permutations avoiding certain generalized 3-patterns and beginning (ending) with an arbitrary pattern having either the greatest or the least letter as its rightmost (leftmost) letter.
LanguageEnglish
Pages267-288
Number of pages22
JournalArs Combinatoria
Volume75
Publication statusPublished - Apr 2005

Fingerprint

Permutation
Exponential Generating Function
Adjacent
Subword
Recursive Formula
Internal
Generalise
Requirements
Arbitrary

Keywords

  • generalized patterns
  • permutation patterns

Cite this

Kitaev, Sergey ; Mansour, Toufik. / Simultaneous avoidance of generalized patterns. In: Ars Combinatoria. 2005 ; Vol. 75. pp. 267-288.
@article{e43aab3cbb8d4753a60fd96251f732a0,
title = "Simultaneous avoidance of generalized patterns",
abstract = "In [BabStein] Babson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. In [Kit1] Kitaev considered simultaneous avoidance (multi-avoidance) of two or more 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. There either an explicit or a recursive formula was given for all but one case of simultaneous avoidance of more than two patterns. In this paper we find the exponential generating function for the remaining case. Also we consider permutations that avoid a pattern of the form x−yz or xy−z and begin with one of the patterns 12...k, k(k−1)...1, 23...k1, (k−1)(k−2)...1k or end with one of the patterns 12...k, k(k−1)...1, 1k(k−1)...2, k12...(k−1). For each of these cases we find either the ordinary or exponential generating functions or a precise formula for the number of such permutations. Besides we generalize some of the obtained results as well as some of the results given in [Kit3]: we consider permutations avoiding certain generalized 3-patterns and beginning (ending) with an arbitrary pattern having either the greatest or the least letter as its rightmost (leftmost) letter.",
keywords = "generalized patterns, permutation patterns",
author = "Sergey Kitaev and Toufik Mansour",
year = "2005",
month = "4",
language = "English",
volume = "75",
pages = "267--288",
journal = "Ars Combinatoria",
issn = "0381-7032",

}

Simultaneous avoidance of generalized patterns. / Kitaev, Sergey; Mansour, Toufik.

In: Ars Combinatoria, Vol. 75, 04.2005, p. 267-288.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Simultaneous avoidance of generalized patterns

AU - Kitaev, Sergey

AU - Mansour, Toufik

PY - 2005/4

Y1 - 2005/4

N2 - In [BabStein] Babson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. In [Kit1] Kitaev considered simultaneous avoidance (multi-avoidance) of two or more 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. There either an explicit or a recursive formula was given for all but one case of simultaneous avoidance of more than two patterns. In this paper we find the exponential generating function for the remaining case. Also we consider permutations that avoid a pattern of the form x−yz or xy−z and begin with one of the patterns 12...k, k(k−1)...1, 23...k1, (k−1)(k−2)...1k or end with one of the patterns 12...k, k(k−1)...1, 1k(k−1)...2, k12...(k−1). For each of these cases we find either the ordinary or exponential generating functions or a precise formula for the number of such permutations. Besides we generalize some of the obtained results as well as some of the results given in [Kit3]: we consider permutations avoiding certain generalized 3-patterns and beginning (ending) with an arbitrary pattern having either the greatest or the least letter as its rightmost (leftmost) letter.

AB - In [BabStein] Babson and Steingrimsson introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. In [Kit1] Kitaev considered simultaneous avoidance (multi-avoidance) of two or more 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. There either an explicit or a recursive formula was given for all but one case of simultaneous avoidance of more than two patterns. In this paper we find the exponential generating function for the remaining case. Also we consider permutations that avoid a pattern of the form x−yz or xy−z and begin with one of the patterns 12...k, k(k−1)...1, 23...k1, (k−1)(k−2)...1k or end with one of the patterns 12...k, k(k−1)...1, 1k(k−1)...2, k12...(k−1). For each of these cases we find either the ordinary or exponential generating functions or a precise formula for the number of such permutations. Besides we generalize some of the obtained results as well as some of the results given in [Kit3]: we consider permutations avoiding certain generalized 3-patterns and beginning (ending) with an arbitrary pattern having either the greatest or the least letter as its rightmost (leftmost) letter.

KW - generalized patterns

KW - permutation patterns

UR - https://personal.cis.strath.ac.uk/sergey.kitaev/index_files/Papers/simultaneous_avoid_gen_patterns.pdf

UR - http://www.combinatorialmath.ca/arscombinatoria/vol75.html

M3 - Article

VL - 75

SP - 267

EP - 288

JO - Ars Combinatoria

T2 - Ars Combinatoria

JF - Ars Combinatoria

SN - 0381-7032

ER -