Generalized Pattern Avoidance

Anders Claesson

Research output: Contribution to journalArticlepeer-review

90 Citations (Scopus)


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.
Original languageEnglish
Pages (from-to)961–971
Number of pages11
JournalEuropean Journal of Combinatorics
Issue number7
Publication statusPublished - Oct 2001


  • Babson Steingrimsson patterns
  • generalized permutation patterns
  • pattern avoidance


Dive into the research topics of 'Generalized Pattern Avoidance'. Together they form a unique fingerprint.

Cite this