Partially ordered generalized patterns

Research output: Contribution to journalArticle

26 Citations (Scopus)

Abstract

We introduce partially ordered generalized patterns (POGPs), which further generalize the generalized permutation patterns (GPs) introduced by Babson and Steingrímsson [Sémin. Lotharingien Combin. B44b (2000) 18]. A POGP p is a GPe some of whose letters are incomparable. Thus, in an occurrence of p in a permutation π, two letters that are incomparable in p pose no restrictions on the corresponding letters in π. We describe many relations between POGPs and GPs and give general theorems about the number of permutations avoiding certain classes of POGPs. These theorems have several known results as corollaries but also give many new results. We also give the generating function for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes, provided we know the exponential generating function for the number of permutations that avoid p.
LanguageEnglish
Pages212-229
Number of pages18
JournalDiscrete Mathematics
Volume298
Issue number1-3
DOIs
Publication statusPublished - 6 Aug 2005

Fingerprint

Exponential functions
Permutation
Exponential Generating Function
Theorem
Generating Function
Corollary
Entire
Restriction
Generalise

Keywords

  • permutations
  • non-overlapping occurrences of patterns
  • POGP
  • generalized patterns

Cite this

Kitaev, Sergey. / Partially ordered generalized patterns. In: Discrete Mathematics. 2005 ; Vol. 298, No. 1-3. pp. 212-229.
@article{14ab922c20d540ed882cdc54577ec151,
title = "Partially ordered generalized patterns",
abstract = "We introduce partially ordered generalized patterns (POGPs), which further generalize the generalized permutation patterns (GPs) introduced by Babson and Steingr{\'i}msson [S{\'e}min. Lotharingien Combin. B44b (2000) 18]. A POGP p is a GPe some of whose letters are incomparable. Thus, in an occurrence of p in a permutation π, two letters that are incomparable in p pose no restrictions on the corresponding letters in π. We describe many relations between POGPs and GPs and give general theorems about the number of permutations avoiding certain classes of POGPs. These theorems have several known results as corollaries but also give many new results. We also give the generating function for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes, provided we know the exponential generating function for the number of permutations that avoid p.",
keywords = "permutations, non-overlapping occurrences of patterns, POGP, generalized patterns",
author = "Sergey Kitaev",
year = "2005",
month = "8",
day = "6",
doi = "10.1016/j.disc.2004.03.017",
language = "English",
volume = "298",
pages = "212--229",
journal = "Discrete Mathematics",
issn = "0012-365X",
number = "1-3",

}

Partially ordered generalized patterns. / Kitaev, Sergey.

In: Discrete Mathematics, Vol. 298, No. 1-3, 06.08.2005, p. 212-229.

Research output: Contribution to journalArticle

TY - JOUR

T1 - Partially ordered generalized patterns

AU - Kitaev, Sergey

PY - 2005/8/6

Y1 - 2005/8/6

N2 - We introduce partially ordered generalized patterns (POGPs), which further generalize the generalized permutation patterns (GPs) introduced by Babson and Steingrímsson [Sémin. Lotharingien Combin. B44b (2000) 18]. A POGP p is a GPe some of whose letters are incomparable. Thus, in an occurrence of p in a permutation π, two letters that are incomparable in p pose no restrictions on the corresponding letters in π. We describe many relations between POGPs and GPs and give general theorems about the number of permutations avoiding certain classes of POGPs. These theorems have several known results as corollaries but also give many new results. We also give the generating function for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes, provided we know the exponential generating function for the number of permutations that avoid p.

AB - We introduce partially ordered generalized patterns (POGPs), which further generalize the generalized permutation patterns (GPs) introduced by Babson and Steingrímsson [Sémin. Lotharingien Combin. B44b (2000) 18]. A POGP p is a GPe some of whose letters are incomparable. Thus, in an occurrence of p in a permutation π, two letters that are incomparable in p pose no restrictions on the corresponding letters in π. We describe many relations between POGPs and GPs and give general theorems about the number of permutations avoiding certain classes of POGPs. These theorems have several known results as corollaries but also give many new results. We also give the generating function for the entire distribution of the maximum number of non-overlapping occurrences of a pattern p with no dashes, provided we know the exponential generating function for the number of permutations that avoid p.

KW - permutations

KW - non-overlapping occurrences of patterns

KW - POGP

KW - generalized patterns

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

U2 - 10.1016/j.disc.2004.03.017

DO - 10.1016/j.disc.2004.03.017

M3 - Article

VL - 298

SP - 212

EP - 229

JO - Discrete Mathematics

T2 - Discrete Mathematics

JF - Discrete Mathematics

SN - 0012-365X

IS - 1-3

ER -