The X-class and almost-increasing permutations

DOI10.1007/S00026-011-0082-9zbMATH Open1233.05011arXiv0710.5168OpenAlexW2593657431MaRDI QIDQ659614FDOQ659614

Authors: Sergi Elizalde 

Publication date: 24 January 2012

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

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.

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

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

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)

Cites Work

• Title not available (Why is that?)
• Combinatorial aspects of continued fractions. (Reprint)
• Some equinumerous pattern-avoiding classes of permutations

Cited In (18)

• 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
• Combinatorial generation via permutation languages. I: Fundamentals
• Hankel and Toeplitz X-rays of permutations
• 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 bijection between evil-avoiding and rectangular permutations
• A generating tree approach to \(k\)-nonnesting partitions and permutations
• On the X-rays of permutations
• A combinatorial classification of 2-regular simple modules for Nakayama algebras
• Growth rates of geometric grid classes of permutations
• Unimodal permutations and almost-increasing cycles
• Unknotted cycles
• Enumerating two permutation classes by the number of 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)