Annals of Combinatorics Layered Restrictions and Chebyshev Polynomials

AMS Subject Classication: 05A05, 05A15, 30B70, 42C05 Dedicated to the memory of Gian-Carlo Rota Abstract. 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 nd 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