Enumerating Permutations Avoiding More Than Three Babson-Steingrímsson Patterns
Antonio Bernini and Elisa Pergola
Dipartimento di Sistemi e Informatica
Università di Firenze
viale G. B. Morgagni 65
Claesson and Mansour recently proposed some conjectures about
the enumeration of the permutations avoiding more than three
Babson-Steingrímsson patterns (generalized patterns of type
(1,2) or (2,1)). The avoidance of one, two or three patterns
has already been considered. Here, the cases of four and five
forbidden patterns are solved and the exact enumeration of the
permutations avoiding them is given, confirming the conjectures of
Claesson and Mansour. The approach we use can be easily extended
to the cases of more than five forbidden patterns.
Full version: pdf,
(Concerned with sequences
Received April 27 2007;
revised version received June 11 2007.
Published in Journal of Integer Sequences, June 11 2007.
Journal of Integer Sequences home page