Restricted 1-3-2 Permutations and Generalized Patterns

Toufik Mansour

LaBRI, Universit谷 Bordeaux I, 351 cours de la Lib谷ration, 33405 Talence Cedex, France

toufik@labri.fr

Annals of Combinatorics 6 (1) p.65-76 March, 2002

Abstract:

Recently, Babson and Steingrimsson (see [2]) introduced generalized permutations
patterns that allow the requirement that two adjacent letters in a pattern must
be adjacent in the permutation. We study generating functions for the number of
permutations on *n* letters avoiding 1-3-2 (or containing 1-3-2 exactly once)
and an arbitrary generalized pattern
on *k* letters, or containing
exactly once. In several cases, the generating function depends only on *k*
and can be expressed via Chebyshev polynomials of the second kind, and the generating
function of Motzkin numbers.

References:

1. M. Böna, The permutation classes equinumerous to the smooth class, Elect. J. Combin. 5 (1998) #R31.

2. E. Babson and E. Steingrimsson, Generalized permutation patterns and a classification of the Mahonian statistics, S谷m. Lothar. Combin. B44b (2000) 18 pp.

3. E, Barcucci, A. Del Lungo, E. Pergola, and R. Pinzani, Directed animals, forests and permutations, Discrete Math. 204 (1999) 41每71.

4. A. Claesson, Generalized pattern avoidance, Europ. J. Combin. 22 (2001) 961每971.

5. A. Claesson and T. Mansour, Permutations avoiding a pair of generalized patterns of length three with exactly one dash, preprint, CO/0107044.

6. T. Chow and J. West, Forbidden subsequences and Chebyshev polynomials, Discrete Math. 204 (1999) 119每128.

7. S. Kitaev, Multi-avoidance of generalized patterns, Discrete Math., to appear.

8. D.E. Knuth, The Art of Computer Programming, 2nd Ed., Addison Wesley, Reading, MA, 1973.

9. C. Krattenthaler, Permutations with restricted patterns and Dyck paths, preprint, CO/0002200.

10. D. Kremer, Permutations with forbidden subsequnces and a generalized Schröder number, Discrete Math. 218 (2000) 121每130.

11. T. Mansour and A. Vainshtein, Restricted permutations, continued fractions, and Chebyshev polynomials, Elect. J. Combin. 7 (2000) #R17.

12. T. Mansour and A. Vainshtein, Restricted 132-avoiding permutations, Adv. Appl. Math. 126 (2001) 258每269.

13. T. Mansour and A. Vainshtein, Layered restrictions and Chebychev polynomials, Ann. Combin. 5 (2001) 451每458.

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

15. A. Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Math. Theor. Comput. Sci. 3 (1999) 151每154.

16. A. Robertson, H. Wilf, and D. Zeilberger, Permutation patterns and continuous fractions, Elect. J. Combin. 6 (1999), #R38.

17. J. West, Generating trees and forbidden subsequences, Discrete Math. 157 (1996) 363每372.