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
50134 Firenze
Italy
Abstract:
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,
dvi,
ps,
latex
(Concerned with sequences
A000027
A000045
A000079
A000124
A001405 and
A094373
.)
Received April 27 2007;
revised version received June 11 2007.
Published in Journal of Integer Sequences, June 11 2007.
Return to
Journal of Integer Sequences home page