Layered restrictions and Chebyshev polynomials

DOI10.1007/S00026-001-8021-9MaRDI QIDQ1600825zbMATH OpenOpenAlexFDO

Authors Toufik Mansour, Alek Vainshtein

Publication date 16 June 2002

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/math/0008173

zbMATH Keywords

Chebyshev polynomialsenumerationgenerating functionspattern avoidancepermutations

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Continued fractions; complex-analytic aspects (30B70) Orthogonal functions and polynomials, general theory of nontrigonometric harmonic analysis (42C05)

Abstract: A permutation is called layered if it consists of the disjoint union of substrings (layers) so that the entries decrease within each layer, and increase between the layers. We find the generating function for the number of permutations on $n$ letters avoiding $(1,2,3)$ and a layered permutation on $k$ letters. In the most interesting case of two layers, the generating function depends only on $k$ and is expressed via Chebyshev polynomials of the second kind.

Recommendations

• Restricted permutations and Chebyshev polynomials
• Restricted even permutations and Chebyshev polynomials
• Restricted colored permutations and Chebyshev polynomials
• Restricted 132-alternating permutations and Chebyshev polynomials
• scientific article; zbMATH DE number 2127715

Cited in

(10)

• Enumeration of permutations containing a prescribed number of occurrences of a pattern of length three
• Restricted permutations and Chebyshev polynomials
• The generalized lucky ticket problem, perfect matchings, and closure relations satisfied by the Chebyshev and \(q\)-Hermite polynomials
• Restricted 132-avoiding \(k\)-ary words, Chebyshev polynomials, and continued fractions
• Horse paths, restricted 132-avoiding permutations, continued fractions, and Chebyshev polynomials
• Restricted even permutations and Chebyshev polynomials
• Dyck paths and restricted permutations
• Restricted Motzkin permutations, Motzkin paths, continued fractions, and Chebyshev polyno\-mials
• Enumeration and Wilf-classification of permutations avoiding four patterns of length 4
• Restricted 132-avoiding permutations

This page was built for publication: Layered restrictions and Chebyshev polynomials

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1600825)