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

cycle diagrampattern-avoiding permutationpicture 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

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

Cited in

(21)

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

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)