<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 11 Issue 3-4" %>
Generating Trees for Permutations Avoiding Generalized Patterns
Sergi Elizalde
Department of Mathematics, Dartmouth College, Hanover NH 03755, USA Centre de Recerca Matematica, Bellaterra E-08193, Spain
Annals of Combinatorics 11 (3-4) p.435-458 September, 2007
AMS Subject Classification:05A15, 05A05, 39B72
We construct generating trees with one, two, and three labels for some classes of permutations avoiding generalized patterns of lengths 3 and 4. These trees are built by adding at each level an entry to the right end of the permutation, which allows us to incorporate the adjacency condition about some entries in an occurrence of a generalized pattern. We use these trees to find functional equations for the generating functions enumerating these classes of permutations with respect to different parameters. In several cases we solve them using the kernel method and some ideas of Bousquet-Mélou [4]. We obtain refinements of known enumerative results and find new ones.
Keywords: generating trees, generalized patterns, pattern avoidance, multiple labels, kernel method, functional equations


1. C. Banderier, M. Bousquet-Mélou, A. Denise, P. Flajolet, D. Gardy, and D. Gouyou- Beauchamps, Generating functions of generating trees, Discrete Math. 246 (1-3) (2002) 29-55.

2. C. Banderier and P. Flajolet, Basic analytic combinatorics of directed lattice paths, Theoret. Comput. Sci. 281 (1-2) (2002) 37-80.

3. A. Bernini, L. Ferrari, and R. Pinzani, Enumerating permutations avoiding three Babson- Steingrímsson patterns, Ann. Combin. 9 (2) (2005) 137-162.

4. M. Bousquet-Mélou, Four classes of pattern-avoiding permutations under one roof: generating trees with two labels, Electron. J. Combin. 9 (2) (2003) #R19.

5. M. Bousquet-Mélou and M. Petkovšek, Linear recurrences with constant coefficients: the multivariate case, Discrete Math. 225 (1-3) (2000) 51-75.

6. A. Burstein, S. Elizalde, and T. Mansour, Restricted Dumont permutations, Dyck paths, and noncrossing partitions, Discrete Math. 306 (22) (2006) 2851-2869.

7. D. Callan, Two bijections for Dyck path parameters, arXiv:math.CO/0406381v2.

8. A. Claesson, Generalised pattern avoidance, Europ. J. Combin. 22 (7) (2001) 961-971.

9. A. Claesson and T. Mansour, Enumerating permutations avoiding a pair of Babson- Steingrímsson patterns, Ars Combin. 77 (2005) 17-31.

10. S. Elizalde, Asymptotic enumeration of permutations avoiding generalized patterns, Adv. Appl. Math. 36 (2006) 138-155.

11. S. Elizalde and T. Mansour, Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials, Discrete Math. 305 (2005) 170-189.

12. S. Elizalde and M. Noy, Consecutive subwords in permutations, Adv. Appl. Math. 30 (2003) 110-125.

13. G. Firro and T. Mansour, Three-letter-pattern-avoiding permutations and functional equations, Electron. J. Combin. 13 (2006) #R51.

14. C. Krattenthaler, Permutations with restricted patterns and Dyck paths, Adv. Appl. Math. 27 (2) (2001) 510-530.

15. T. Mansour, Restricted 1-3-2 permutations and generalized patterns, Ann. Combin. 6 (1) (2002) 65-76.

16. N.J.A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, San Diego, 1995.

17. J. West, Generating trees and the Catalan and Schröder numbers, Discrete Math. 146 (1) (1995) 247-262.

18. J. West, Generating trees and forbidden subsequences, Discrete Math. 157 (1) (1996) 363- 374.