Restricted permutations and Chebyshev polynomials

Abstract

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

17 pages, 5 figures

Cited by in corpus (14)

• Patterns in random permutations avoiding the pattern 132
• On the diagram of 132-avoiding permutations
• Enumeration schemes for restricted permutations
• Some statistics on restricted 132 involutions
• Involutions Restricted by 3412, Continued Fractions, and Chebyshev Polynomials
• Restricted 3412-Avoiding Involutions: Continued Fractions, Chebyshev Polynomials and Enumerations
• Restricted 132-alternating permutations and Chebyshev polynomials
• New equivalences for pattern avoiding involutions
• Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polynomials
• Locally Convex Words and Permutations
• Classical pattern distributions in ${\mathcal{S}}_n(132)$ and ${\mathcal{S}}_n(123)$
• Restricted 132-Dumont permutations
• 321-polygon-avoiding permutations and Chebyshev polynomials
• Permutations Which Avoid 1243 and 2143, Continued Fractions, and Chebyshev Polynomials