Explicit enumeration of 321, hexagon-avoiding permutations

DOI10.1016/J.DISC.2003.06.003MaRDI QIDQ1827678zbMATH OpenOpenAlexFDO

Authors Julian West, Zvezdelina E. Stankova

Publication date 6 August 2004

Published in Discrete Mathematics (Search for Journal in Brave)

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

zbMATH Keywords

321, hexagon-avoiding permutationsForbidden subsequencesHeapsKazhdan-Lusztig polynomialsLinear recurrenceSchubert varieties

Mathematics Subject Classification ID

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

Abstract: The 321,hexagon-avoiding (321-hex) permutations were introduced and studied by Billey and Warrington in as a class of elements of S_n whose Kazhdan-Lusztig and Poincare polynomials and the singular loci of whose Schubert varieties have certain fairly simple and explicit descriptions. This paper provides a 7-term linear recurrence relation leading to an explicit enumeration of the 321-hex permutations. A complete description of the corresponding generating tree is obtained as a by-product of enumeration techniques used in the paper, including Schensted's 321-subsequences decomposition, a 5-parameter generating function and the symmetries of the octagonal patterns avoided by the 321-hex permutations.

Recommendations

• 321-polygon-avoiding permutations and Chebyshev polynomials
• scientific article; zbMATH DE number 2127715
• 321-avoiding affine permutations and their many heaps
• On multi-avoidance of generalized patterns.
• Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations

Cites work

• 321-polygon-avoiding permutations and Chebyshev polynomials
• A new class of Wilf-equivalent permutations
• Applications of the Theory of Morse to Symmetric Spaces
• Classification of forbidden subsequences of length 4
• Forbidden subsequences
• Generating trees and forbidden subsequences
• Generating trees and the Catalan and Schröder numbers
• scientific article; zbMATH DE number 3721082 (Why is no real title available?)
• scientific article; zbMATH DE number 47598 (Why is no real title available?)
• scientific article; zbMATH DE number 568838 (Why is no real title available?)
• scientific article; zbMATH DE number 1026567 (Why is no real title available?)
• scientific article; zbMATH DE number 1770478 (Why is no real title available?)
• scientific article; zbMATH DE number 3327350 (Why is no real title available?)
• Kazhdan-Lusztig polynomials for 321-hexagon-avoiding permutations
• Longest Increasing and Decreasing Subsequences
• Representations of Coxeter groups and Hecke algebras
• Some combinatorial properties of Schubert polynomials
• The number of Baxter permutations
• The permutations 123p₄ p_m and 321p₄ p_m are Wilf-equivalent
• Wilf-equivalence for singleton classes

Cited in

(5)

• 321-avoiding affine permutations, heaps, and periodic parallelogram polyominoes
• Finitely labeled generating trees and restricted permutations
• Labelled well-quasi-order for permutation classes
• Enumeration Schemes for Restricted Permutations
• The enumeration of maximally clustered permutations

This page was built for publication: Explicit enumeration of 321, hexagon-avoiding permutations

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