  A 321-k-gon-avoiding permutation pi avoids 321 and the following four
patterns: k(k+2)(k+3)...(2k-1)1(2k)23...(k+1),
k(k+2)(k+3)...(2k-1)(2k)123...(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 [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.
