<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 9 Issue 2" %>
Enumerating Permutations Avoiding Three Babson-Steingrimsson Patterns
Antonio Bernini1, Luca Ferrari2, and Renzo Pinzani1
1Università di Firenze, Dipartimento di Sistemi e Informatica, viale G. B. Morgagni, 65, 50134, Firenze, Italy
{bernini, pinzani}@dsi.unifi.it
2Università di Siena, Dipartimento di Scienze Matemathiche ed Informatiche, Pian dei Mantellini 44, 53100, Siena, Italy
Annals of Combinatorics 9 (2) p.137-162 June, 2005
AMS Subject Classification: 05A05, 05A15
We settle some conjectures formulated by A. Claesson and T. Mansour concerning generalized pattern avoidance of permutations. In particular, we solve the problem of the enumeration of permutations avoiding three generalized patterns of type (1, 2) or (2, 1) by using ECO method and a graphical representation of permutations.
Keywords: generalized patterns avoidance, permutations, succession rules, Fibonacci and Motzkin numbers


1. E. Babson and E. Steingrímsson, Generalized permutation patterns and a classification of the Mahonian statistics, Sém. Lothar. Combin. 44 (2000) Art. B44b, 18 pp. (electronic).

2. E. Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, ECO: A methodology for the enumeration of combinatorial objects, Int. J. Differ. Equ. Appl. 5 (1999) 435--490.

3. A. Claesson, Generalized pattern avoidance, Europ. J. Combin. 22 (2001) 961--71.

4. A. Claesson and T. Mansour, Enumerating permutations avoiding a pair of Babson- Steingrímsson patterns, Ars Combinatoria, to appear.

5. L. Ferrari, E. Pergola, R. Pinzani, and S. Rinaldi, An algebraic characterization of the set of succession rules, Theoret. Comput. Sci. 281 (2002) 351--367.

6. M. Fulmek, Enumeration of permutations containing a prescribed number of occurences of a pattern of length 3, Adv. in Appl. Math. 30 (2003) 607--632.

7. C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. in Appl. Math. 25 (2001) 510--530.

8. E. Pergola, R. Pinzani, and S. Rinaldi, Approximating algebraic functions by means of rational ones, Theoret. Comput. Sci. 270 (2002) 643--657.

9. R. Simion and F.W. Schmidt, Restricted permutations, Europ. J. Combin. 6 (1985) 383--406.

10. Z. Stankova and J. West, Explicit enumeration of 321, hexagon-avoiding permutations, Discrete Math. 280 (2004) 165--189.