Séminaire Lotharingien de Combinatoire, B47c (2002), 17 pp.

Toufik Mansour and Alek Vainshtein

Restricted Permutations and Chebyshev Polynomials

Abstract. We study generating functions for the number of permutations in Sn subject to two restrictions. One of the restrictions belongs to S3, while the other belongs to Sk. It turns out that in a large variety of cases the answer can be expressed via Chebyshev polynomials of the second kind.

Received: June 26, 2001; Revised: December 12, 2001; Accepted: January 3, 2002.

The following versions are available: