Tuyển tập các báo cáo nghiên cứu khoa học ngành toán học tạp chí toán học quốc tế đề tài: 321-polygon-avoiding permutations and Chebyshev polynomials | 321-polygon-avoiding permutations and Chebyshev polynomials Toufik Mansour LaBRI Universite Bordeaux I 351 cours de la Liberation 33405 Talence Cedex France toufik@ Zvezdelina Stankova Mills College Oakland CA stankova@ Submitted Jul 22 2002 Accepted Jan 6 2003 Published Jan 22 2003 MR Subject Classifications 05A05 05A15 30B70 42C05 Abstract A 321-k-gon-avoiding permutation n avoids 321 and the following four patterns k k 2 k 3 2k - 1 1 2k 23 k - 1 k 1 k k 2 k 3 2k - 1 2k 12 k - 1 k 1 k 1 k 2 k 3 2k - 1 1 2k 23 k k 1 k 2 k 3 2k - 1 2k 123 k. The 321-4-gon-avoiding permutations were introduced and studied by Billey and Warrington BW as a class of elements of the symmetric group whose Kazhdan-Lusztig Poincare polynomials and the singular loci of whose Schubert varieties have fairly simple formulas and descriptions. Stankova and West SW1 gave an exact enumeration in terms of linear recurrences with constant coefficients for the cases k 2 3 4. In this paper we extend these results by finding an explicit expression for the generating function for the number of 321-k-gon-avoiding permutations on n letters. The generating function is expressed via Chebyshev polynomials of the second kind. 1 Introduction Definition 1 Let a G Sn and T E Sk be two permutations. Then a contains T if there exists a subsequence 1 ii i2 . ik n such that ai . aik is order-isomorphic to T in such a context T is usually called a pattern a avoids T or is T-avoiding if a does not contain such a subsequence. The set of all T-avoiding permutations in Sn is THE ELECTRONIC JOURNAL OF COMBINATORICS 9 2 2003 R5 1 denoted by Sn T . For a collection of patterns T a avoids T if a avoids all T E T the corresponding subset of Sn is denoted by Sn T . While the case of permutations avoiding a single pattern has attracted much attention for example see BaWe BWX S SW2 the case of multiple pattern avoidance remains less investigated. In particular it is natural to consider permutations avoiding .
