Back to overview

Operators of equivalent sorting power and related Wilf-equivalences.

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Author Michael Albert, Mathilde Bouvel,
Project Permutation classes: from structure to combinatorial properties
Show all

Original article (peer-reviewed)

Journal Electronic Journal of Combinatorics
Volume (Issue) 21(4)
Page(s) P4.11
Title of proceedings Electronic Journal of Combinatorics

Open Access


We study sorting operators A on permutations that are obtained composing Knuth's stack sorting operator S and the reversal operator R, as many times as desired. For any such operator A, we provide a size-preserving 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 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.