321-polygon-avoiding permutations and Chebyshev polynomials

Toufik Mansour ; Zvezdelina Stankova

The electronic journal of combinatorics, Permutation Patterns, Tome 9 (2002) no. 2

Résumé

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.

Détail

DOI : 10.37236/1677

Classification : 05A05, 05A15, 42C05
Mots-clés : number of polygon-avoiding permutations, linear recurrence