$321$-Polygon-Avoiding Permutations and Chebyshev Polynomials

Abstract

A $321$-$k$-gon-avoiding permutation $\pi$ avoids $321$ and the following four patterns: $$k(k+2)(k+3)\cdots(2k-1)1(2k)23\cdots(k-1)(k+1),$$ $$k(k+2)(k+3)\cdots(2k-1)(2k)12\cdots(k-1)(k+1),$$ $$(k+1)(k+2)(k+3)\cdots(2k-1)1(2k)23\cdots k,$$ $$(k+1)(k+2)(k+3)\cdots(2k-1)(2k)123\cdots 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, Poincaré polynomials, and the singular loci of whose Schubert varieties have fairly simple formulas and descriptions. Stankova and West [SW] 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.