<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 6 Issue 1" %>
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
AMS Subject Classification: 05A05, 05A15, 42C05
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.
Keywords: restricted permutations, generalized patterns, Chebyshev polynomials

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.