<%@ Page Language="C#" MasterPageFile="~/Main.master" AutoEventWireup="true" Title="Volume 5 Issue 3" %>
Layered Restrictions and Chebyshev Polynomials
Toufik Mansour1 and Alek Vainshtein2
1LaBRI, University Bordeaux 1, 351 cours de la Liberation, 33405 Talence Cedex, France
2Department of Mathematics and Department of Computer Science, University of Haifa, Haifa,Israel 31905
Annals of Combinatorics 5 (3) p.451-458 September, 2001
AMS Subject Classification: 05A05, 05A15, 30B70, 42C05
A permutation is called layered if it consists of the disjoint union of substrings (layers) so that the entries decrease within each layer, and increase between the layers. We find the generating function for the number of permutations on n letters avoiding (1,2,3) and a layered permutation on k letters. In the most interesting case of two layers, the generating function depends only on k and is expressed via Chebyshev polynomials of the second kind.
Keywords: permutations, pattern avoidance, enumeration, generating functions, Chebyshev polynomials


1.  M. Bóna, The solution of a conjecture of Stanley andWilf for all layered patterns, J. Combin. Theory Ser. A 85 (1999) 96–104.

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

3.  P. Erdös and G. Szekeres, A combinatorial problem in geometry, Compositio Math. 2 (1935) 463–470.

4.  D. Knuth, The Art of Computer Programming, Vol. 3, Addison Wesley, Reading, MA, 1973.

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

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

7.  J. Riordan, Combinatorial Identities, John Wiley, New York, 1968.

8.  F. Schmidt and R. Simion, Restricted permutations, Europ. J. Combin. 6 (1985) 383–406.