Generalised Pattern Avoidance

Abstract

Recently, Babson and Steingrimsson have introduced generalised permutation patterns that allow the requirement that two adjacent letters in a pattern must be adjacent in the permutation. We 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. We also give some results for the number of permutations avoiding two different patterns. Relations are exhibited to several well studied combinatorial structures, such as set partitions, Dyck paths, Motzkin paths, and involutions. Furthermore, a new class of set partitions, called monotone partitions, is defined and shown to be in one-to-one correspondence with non-overlapping partitions.

Cited by in corpus (19)

• Simultaneous avoidance of generalized patterns
• On multi-avoidance of generalized patterns
• Continued fractions, statistics, and generalized patterns
• The Peano curve and counting occurrences of some patterns
• A Wilf equivalence related to two stack sortable permutations
• Generalized pattern avoidance with additional restrictions
• Counting the occurrences of generalized patterns in words generated by a morphism
• Some statistics on restricted 132 involutions
• Restricted permutations by patterns of type $(2,1)$
• Introduction to Partially Ordered Patterns
• Logarithmic behavior of some combinatorial sequences
• restricted 1-3-2 permutations and generalized patterns
• Restricted 132-alternating permutations and Chebyshev polynomials
• Partially Ordered generalized patterns and k-ary words
• Restricted 132-Dumont permutations
• Generating trees for permutations avoiding generalized patterns
• Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials
• Continued fractions and generalized patterns
• The sigma-sequence and counting occurrences of some patterns, subsequences and subwords