The X-class and almost-increasing permutations

DOI10.1007/S00026-011-0082-9MaRDI QIDQ659614zbMATH OpenOpenAlexFDO

Authors Sergi Elizalde

Publication date 24 January 2012

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

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

zbMATH Keywords

pattern-avoiding permutationcycle diagrampicture classX-class

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15) Combinatorial identities, bijective combinatorics (05A19)

Abstract: In this paper we give a bijection between the class of permutations that can be drawn on an X-shape and a certain set of permutations that appears in [Knuth] in connection to sorting algorithms. A natural generalization of this set leads us to the definition of almost-increasing permutations, which is a one-parameter family of permutations that can be characterized in terms of forbidden patterns. We find generating functions for almost-increasing permutations by using their cycle structure to map them to colored Motzkin paths. We also give refined enumerations with respect to the number of cycles, fixed points, excedances, and inversions.

Recommendations

• Unimodal permutations and almost-increasing cycles
• On the X-rays of permutations
• Some permutations with forbidden subsequences and their inversion number
• Almost avoiding pairs of permutations
• Simple permutations and pattern restricted permutations

Cites work

• scientific article; zbMATH DE number 3303654 (Why is no real title available?)
• Combinatorial aspects of continued fractions. (Reprint)
• Some equinumerous pattern-avoiding classes of permutations

Cited in

(18)

• Enumerating two permutation classes by the number of cycles
• Geometric grid classes of permutations
• Separable \(d\)-permutations and guillotine partitions
• Permutation patterns, Stanley symmetric functions, and generalized Specht modules
• The enumeration of permutations avoiding 3124 and 4312
• Hankel and Toeplitz X-rays of permutations
• Combinatorial generation via permutation languages. I: Fundamentals
• Labelled well-quasi-order for permutation classes
• Square permutations are typically rectangular
• Scaling limits of permutation classes with a finite specification: a dichotomy
• On the centrosymmetric permutations in a class
• A generating tree approach to k-nonnesting partitions and permutations
• A bijection between evil-avoiding and rectangular permutations
• On the X-rays of permutations
• Growth rates of geometric grid classes of permutations
• A combinatorial classification of 2-regular simple modules for Nakayama algebras
• Unimodal permutations and almost-increasing cycles
• Unknotted cycles

This page was built for publication: The X-class and almost-increasing permutations

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