On multi-avoidance of generalized patterns

Sergey Kitaev, Toufik Mansour

Research output: Contribution to journalArticle

2 Citations (Scopus)

Abstract

In [Kit1] Kitaev discussed simultaneous avoidance of two 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. In three essentially different cases, the numbers of such n-permutations are 2n−1, the number of involutions in n, and 2En, where En is the n-th Euler number. In this paper we give recurrence relations for the remaining three essentially different cases.
To complete the descriptions in [Kit3] and [KitMans], we consider avoidance of a pattern of the form x−y−z (a classical 3-pattern) and beginning or ending with an increasing or decreasing pattern. Moreover, we generalize this problem: we demand that a permutation must avoid a 3-pattern, begin with a certain pattern and end with a certain pattern simultaneously. We find the number of such permutations in case of avoiding an arbitrary generalized 3-pattern and beginning and ending with increasing or decreasing patterns.
LanguageEnglish
Pages321-350
Number of pages30
JournalArs Combinatoria
Volume76
Publication statusPublished - Jul 2005

Fingerprint

Permutation
Subword
Euler numbers
Recurrence relation
Involution
Internal
Generalise
Arbitrary

Keywords

  • generalized patterns
  • increasing pattern
  • decreasing pattern

Cite this

Kitaev, Sergey ; Mansour, Toufik. / On multi-avoidance of generalized patterns. In: Ars Combinatoria. 2005 ; Vol. 76. pp. 321-350.
@article{efbb8cf7cfe94f74b8a53bc2cbd4c8bf,
title = "On multi-avoidance of generalized patterns",
abstract = "In [Kit1] Kitaev discussed simultaneous avoidance of two 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. In three essentially different cases, the numbers of such n-permutations are 2n−1, the number of involutions in n, and 2En, where En is the n-th Euler number. In this paper we give recurrence relations for the remaining three essentially different cases. To complete the descriptions in [Kit3] and [KitMans], we consider avoidance of a pattern of the form x−y−z (a classical 3-pattern) and beginning or ending with an increasing or decreasing pattern. Moreover, we generalize this problem: we demand that a permutation must avoid a 3-pattern, begin with a certain pattern and end with a certain pattern simultaneously. We find the number of such permutations in case of avoiding an arbitrary generalized 3-pattern and beginning and ending with increasing or decreasing patterns.",
keywords = "generalized patterns, increasing pattern, decreasing pattern",
author = "Sergey Kitaev and Toufik Mansour",
year = "2005",
month = "7",
language = "English",
volume = "76",
pages = "321--350",
journal = "Ars Combinatoria",
issn = "0381-7032",

}

Kitaev, S & Mansour, T 2005, 'On multi-avoidance of generalized patterns' Ars Combinatoria, vol. 76, pp. 321-350.

On multi-avoidance of generalized patterns. / Kitaev, Sergey; Mansour, Toufik.

In: Ars Combinatoria, Vol. 76, 07.2005, p. 321-350.

Research output: Contribution to journalArticle

TY - JOUR

T1 - On multi-avoidance of generalized patterns

AU - Kitaev, Sergey

AU - Mansour, Toufik

PY - 2005/7

Y1 - 2005/7

N2 - In [Kit1] Kitaev discussed simultaneous avoidance of two 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. In three essentially different cases, the numbers of such n-permutations are 2n−1, the number of involutions in n, and 2En, where En is the n-th Euler number. In this paper we give recurrence relations for the remaining three essentially different cases. To complete the descriptions in [Kit3] and [KitMans], we consider avoidance of a pattern of the form x−y−z (a classical 3-pattern) and beginning or ending with an increasing or decreasing pattern. Moreover, we generalize this problem: we demand that a permutation must avoid a 3-pattern, begin with a certain pattern and end with a certain pattern simultaneously. We find the number of such permutations in case of avoiding an arbitrary generalized 3-pattern and beginning and ending with increasing or decreasing patterns.

AB - In [Kit1] Kitaev discussed simultaneous avoidance of two 3-patterns with no internal dashes, that is, where the patterns correspond to contiguous subwords in a permutation. In three essentially different cases, the numbers of such n-permutations are 2n−1, the number of involutions in n, and 2En, where En is the n-th Euler number. In this paper we give recurrence relations for the remaining three essentially different cases. To complete the descriptions in [Kit3] and [KitMans], we consider avoidance of a pattern of the form x−y−z (a classical 3-pattern) and beginning or ending with an increasing or decreasing pattern. Moreover, we generalize this problem: we demand that a permutation must avoid a 3-pattern, begin with a certain pattern and end with a certain pattern simultaneously. We find the number of such permutations in case of avoiding an arbitrary generalized 3-pattern and beginning and ending with increasing or decreasing patterns.

KW - generalized patterns

KW - increasing pattern

KW - decreasing pattern

UR - http://arxiv.org/abs/math/0209340

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

M3 - Article

VL - 76

SP - 321

EP - 350

JO - Ars Combinatoria

T2 - Ars Combinatoria

JF - Ars Combinatoria

SN - 0381-7032

ER -