Generalised pattern avoidance

Anders Claesson

To appear at Formal Power Series and Algebraic Combinatorics (FPSAC01), Tempe, Arizona (USA), May 20-26, 2001


Recently, Babson and Steingr\'{\i}msson 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.

Server START Conference Manager
Update Time 23 Feb 2001 at 08:48:04
Start Conference Manager
Conference Systems