Operators of equivalent sorting power and related Wilf-equivalences - Inria - Institut national de recherche en sciences et technologies du numérique Accéder directement au contenu
Communication Dans Un Congrès Discrete Mathematics and Theoretical Computer Science Année : 2013

Operators of equivalent sorting power and related Wilf-equivalences

Résumé

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.
Fichier principal
Vignette du fichier
dmAS0157.pdf (385.05 Ko) Télécharger le fichier
Origine : Fichiers éditeurs autorisés sur une archive ouverte
Loading...

Dates et versions

hal-01229676 , version 1 (17-11-2015)

Identifiants

Citer

Michael Albert, Mathilde Bouvel. Operators of equivalent sorting power and related Wilf-equivalences. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. pp.671-682, ⟨10.46298/dmtcs.2333⟩. ⟨hal-01229676⟩

Collections

CNRS TDS-MACS
62 Consultations
549 Téléchargements

Altmetric

Partager

Gmail Facebook X LinkedIn More