Generalized Pattern Avoidance

Claesson, Anders (2001) Generalized Pattern Avoidance. European Journal of Combinatorics, 22 (7). 961–971. ISSN 0195-6698 (https://doi.org/10.1006/eujc.2001.0515)

Full text not available in this repository.Request a copy

Abstract

Recently, Babson and Steingrımsson have introduced generalized permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We will consider pattern avoidance for such patterns, and give a complete solution for the number of permutations avoiding any single pattern of length three with exactly one adjacent pair of letters. For eight of these 12 patterns the answer is given by the Bell numbers. For the remaining four the answer is given by the Catalan numbers. We also give some results for the number of permutations avoiding two different patterns. These results relate the permutations in question to Motzkin paths, involutions and non-overlapping partitions. Furthermore, we define a new class of set partitions, called monotone partitions, and show that these partitions are in one-to-one correspondence with non-overlapping partitions.

ORCID iDs

Claesson, Anders ORCID logoORCID: https://orcid.org/0000-0001-5797-8673;
  • Item type:Article
    ID code:49805
    Dates:
    Date
    Event
    October 2001
    Published
    Keywords:Babson Steingrimsson patterns, generalized permutation patterns, pattern avoidance, Electronic computers. Computer science, Computational Theory and Mathematics, Geometry and Topology, Theoretical Computer Science
    Subjects:Science > Mathematics > Electronic computers. Computer science
    Department:Faculty of Science > Computer and Information Sciences
    Depositing user: Pure Administrator
    Date deposited:14 Oct 2014 15:18
    Last modified:03 Dec 2022 03:45
    URI:https://strathprints.strath.ac.uk/id/eprint/49805
CORE (COnnecting REpositories)