DMTCS Proceedings, 25th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2013)

Font Size:  Small  Medium  Large

Operators of equivalent sorting power and related Wilf-equivalences

M. Albert, M. Bouvel


We study sorting operators A on permutations that are obtained composing Knuth's stack sorting operator S and the reverse operator R, as many times as desired. For any such operator A, we provide a bijection between the set of permutations sorted by S ˆA and the set of those sorted by S ˆR ˆ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.
Résumé. On étudie les opérateurs A de tri de permutations obtenus en composant l'opérateur S de tri par une pile de Knuth et l'opérateur R de miroir, un certain nombre de fois. Pour tout opérateur A de cette forme, on donne une bijection entre l'ensemble des permutations triées par S ˆA et l'ensemble de celles triées par S ˆR ˆA, démontrant ainsi que ces ensembles ont la même séquence d'énumération, mais aussi que de nombreuses statistiques classiques sur les permutations ont la même distribution sur ces deux ensembles. La description de cette famille de bijections repose sur une bijection apparemment nouvelle entre l'ensemble des permutations qui évitent le motif 231 et l'ensemble de celles qui évitent 132, qui préserve de nombreuses statistiques. On présente aussi d'autres propriétés de cette bijection, en particulier pour trouver des familles de classes de permutations équivalentes au sens de Wilf.

Full Text: PostScript PDF

Valid XHTML 1.0 Transitional