Michael Albert ; Mathilde Bouvel - Operators of equivalent sorting power and related Wilf-equivalences

dmtcs:2333 - Discrete Mathematics & Theoretical Computer Science, January 1, 2013, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013) - https://doi.org/10.46298/dmtcs.2333
Operators of equivalent sorting power and related Wilf-equivalencesArticle

Authors: Michael Albert 1; Mathilde Bouvel 2

  • 1 Department of Computer Science, University of Otago
  • 2 Laboratoire Bordelais de Recherche en Informatique

We study sorting operators $\textrm{A}$ on permutations that are obtained composing Knuth's stack sorting operator \textrmS and the reverse operator $\textrm{R}$, as many times as desired. For any such operator $\textrm{A}$, we provide a bijection between the set of permutations sorted by $\textrm{S} \circ \textrm{A}$ and the set of those sorted by $\textrm{S} \circ \textrm{R} \circ \textrm{A}$, 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 an apparently novel 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 families of Wilf-equivalent permutation classes.


Volume: DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)
Section: Proceedings
Published on: January 1, 2013
Imported on: November 21, 2016
Keywords: permutation,stack,sorting,enumeration,Wilf-equivalence,[INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM]
Funding:
    Source : OpenAIRE Graph
  • Permutation classes: from structure to combinatorial properties; Funder: Swiss National Science Foundation; Code: 151254

2 Documents citing this article

Consultation statistics

This page has been seen 218 times.
This article's PDF has been downloaded 194 times.