Operators of equivalent sorting power and related Wilf-equivalences

Abstract : 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.
Type de document :
Communication dans un congrès
Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.671-682, 2013, DMTCS Proceedings
Liste complète des métadonnées

Littérature citée [12 références]  Voir  Masquer  Télécharger

https://hal.inria.fr/hal-01229676
Contributeur : Alain Monteil <>
Soumis le : mardi 17 novembre 2015 - 10:19:45
Dernière modification le : jeudi 11 janvier 2018 - 06:20:17
Document(s) archivé(s) le : jeudi 18 février 2016 - 11:36:05

Fichier

dmAS0157.pdf
Fichiers éditeurs autorisés sur une archive ouverte

Identifiants

  • HAL Id : hal-01229676, version 1

Collections

Citation

Michael Albert, Mathilde Bouvel. Operators of equivalent sorting power and related Wilf-equivalences. Alain Goupil and Gilles Schaeffer. 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), 2013, Paris, France. Discrete Mathematics and Theoretical Computer Science, DMTCS Proceedings vol. AS, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013), pp.671-682, 2013, DMTCS Proceedings. 〈hal-01229676〉

Partager

Métriques

Consultations de la notice

73

Téléchargements de fichiers

91