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
**AMS Subject Classification:**05A15, 05A05, 39B72
**Keywords: **generating trees, generalized patterns, pattern avoidance, multiple labels, kernel
method, functional equations

sergi.elizalde@dartmouth.edu

Annals of Combinatorics 11 (3-4) p.435-458 September, 2007

Abstract:

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.
References:

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.