<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume7 Issue2" %>
Restricted 132-Alternating Permutations and Chebyshev Polynomials
Toufik Mansour
Matematik, Chalmers tekniska högskola och Göteborgs universitet, 412 96 Göteborg, Sweden
Annals of Combinatorics 7 (2) p.201-227 June, 2003
AMS Subject Classification: 05A05, 05A15, 30B70, 42C05
A permutation is said to be alternating if it starts with rise and then descents and rises come in turn. In this paper we study the generating function for the number of alternating permutations on n letters that avoid or contain exactly once 132 and also avoid or contain exactly once an arbitrary pattern on k letters. In several interesting cases the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.
Keywords: alternating permutations, restricted permutations, generating functions, Chebyshev polynomials


1. D. André, Developments de secx et tanx, C.R. Acad. Sci. Paris 88 (1879) 965--967.

2. D. André, Memire sur les permutations alternées, J. Math. 7 (1881) 167--184.

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

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

5. P. Brändén, A. Claesson, and E. Steingrímsson, Continued fractions and increasing subsequences in permutations, Discrete Math., to appear.

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

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

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

9. D. Kremer, Permutations with forbidden subsequences and a generalized Schröder number, Discrete Math. 218 (2000) 121--130.

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

11. T. Mansour, Continued fractions and generalized patterns, Europ. J. Combin. 23 (3) (2002) 329--344.

12. T. Mansour, Continued fractions, statistics, and generalized patterns, Ars Combin., to appear.

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

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

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

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

17. T. Mansour and A. Vainshtein, Restricted permutations and Chebyshev polynomials, Sémi. Lothar. Combin. B47c (2002).

18. T. Mansour and A. Vainshtein, Counting occurrences of 132 in a permutation, Adv. Appl. Math. 28 (2) (2002) 185--195.

19. A. Robertson, Permutations containing and avoiding 123 and 132 patterns, Discrete Math. Theoret. Comput. Sci. 3 (1999) 151--154.

20. Th. Rivlin, Chebyshev Polynomials: From Approximation Theory to Algebra and Number Theory, John Wiley, New York, 1990.

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

22. N.J.A. Sloane and S. Plouffe, The Encyclopedia of Integer Sequences, Academic Press, New York, 1995.

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

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