Operators of equivalent sorting power and related Wilf-equivalences

zbMATH Open1294.05182arXiv1402.2034MaRDI QIDQ5746166FDOQ5746166

Authors: Mathilde Bouvel, Michael Albert 

Publication date: 18 February 2014

Abstract: We study sorting operators $mathbfA$ on permutations that are obtained composing Knuth's stack sorting operator $mathbfS$ and the reversal operator $mathbfR$, as many times as desired. For any such operator $mathbfA$, we provide a size-preserving bijection between the set of permutations sorted by $mathbfScircmathbfA$ and the set of those sorted by $mathbfScircmathbfRcircmathbfA$, proving that these sets are enumerated by the same sequence, but also that many classical permutation statistics are equidistributed across these two sets. The description of this family of bijections is based on a bijection between the set of permutations avoiding the pattern $231$ and the set of those avoiding $132$ which preserves many permutation statistics. We also present other properties of this bijection, in particular for finding pairs of Wilf-equivalent permutation classes.

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

Recommendations

• Operators of equivalent sorting power and related Wilf-equivalences
• Many-sorted elementary equivalence
• ORDERINGS FOR CLASSES OF AGGREGATION OPERATORS
• Reflections on and of minor-closed classes of multisorted operations
• On a refinement of Wilf-equivalence for permutations
• On Wilf equivalence for alternating permutations
• The complexity of some ordinal determined classes of operators
• On super-strong Wilf equivalence classes of permutations
• On operations and linear extensions of well partially ordered sets

zbMATH Keywords

permutationenumerationsortingstackWilf-equivalence

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Combinatorial identities, bijective combinatorics (05A19)

Cited In (4)

• Reflections on and of minor-closed classes of multisorted operations
• Operators of equivalent sorting power and related Wilf-equivalences
• An infinite family of inv-Wilf-equivalent permutation pairs
• A general theory of Wilf-equivalence for Catalan structures

This page was built for publication: Operators of equivalent sorting power and related Wilf-equivalences

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