Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials

DOI10.1016/J.AAM.2003.09.006zbMATH Open1059.05004arXivmath/0307050OpenAlexW2045976967MaRDI QIDQ705239FDOQ705239

Eric S. Egge

Publication date: 26 January 2005

Published in: Advances in Applied Mathematics (Search for Journal in Brave)

Abstract: Several authors have examined connections among restricted permutations, continued fractions, and Chebyshev polynomials of the second kind. In this paper we prove analogues of these results for involutions which avoid 3412. Our results include a recursive procedure for computing the generating function for involutions which avoid 3412 and any set of additional patterns. We use our results to give enumerations and generating functions for involutions which avoid 3412 and various sets of additional patterns. In many cases we express these generating functions in terms of Chebyshev polynomials of the second kind.

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

zbMATH Keywords

Chebyshev polynomialscontinued fractionsMotzkin pathspattern-avoiding permutationsrestricted permutationsforbidden subsequencespattern-avoiding involutionsrestricted involutions

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Cites Work

• Title not available (Why is that?)
• Restricted permutations
• Permutations with restricted patterns and Dyck paths
• Combinatorial aspects of continued fractions
• Restricted permutations and Chebyshev polynomials
• Restricted 132-avoiding permutations
• Catalan continued fractions and increasing subsequences in permutations
• Some statistics on restricted 132 involutions
• Permutations which avoid 1243 and 2143, continued fractions, and Chebyshev polynomials
• On the diagram of Schröder permutations

Cited In (14)

• Simple permutations and algebraic generating functions
• Restricted involutions and Motzkin paths
• Counting occurrences of 231 in an involution
• Title not available (Why is that?)
• Bivariate generating functions for involutions restricted by 3412
• Counting covered fixed points and covered arcs in an involution
• Crossings and nestings over some Motzkin objects and \(q\)-Motzkin numbers
• Inversion polynomials for 321-avoiding permutations
• Avoiding patterns of length three in compositions and multiset permutations
• Fibonacci numbers, reduced decompositions, and 321/3412 pattern classes
• Symmetric permutations avoiding two patterns
• Maxima and visibility in involutions
• Restricted colored permutations and Chebyshev polynomials
• Inversion formulae on permutations avoiding 321

This page was built for publication: Restricted 3412-avoiding involutions, continued fractions, and Chebyshev polynomials

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