We study sorting operators $\mathbf{A}$ on permutations that are obtained composing Knuth's stack sorting operator $\mathbf{S}$ and the reversal operator $\mathbf{R}$, as many times as desired. For any such operator $\mathbf{A}$, we provide a size-preserving bijection between the set of permutations sorted by $\mathbf{S} \circ \mathbf{A}$ and the set of those sorted by $\mathbf{S} \circ \mathbf{R} \circ \mathbf{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.
@article{10_37236_4119,
author = {Michael Albert and Mathilde Bouvel},
title = {Operators of equivalent sorting power and related {Wilf-equivalences}},
journal = {The electronic journal of combinatorics},
year = {2014},
volume = {21},
number = {4},
doi = {10.37236/4119},
zbl = {1298.05005},
url = {http://geodesic.mathdoc.fr/articles/10.37236/4119/}
}
TY - JOUR
AU - Michael Albert
AU - Mathilde Bouvel
TI - Operators of equivalent sorting power and related Wilf-equivalences
JO - The electronic journal of combinatorics
PY - 2014
VL - 21
IS - 4
UR - http://geodesic.mathdoc.fr/articles/10.37236/4119/
DO - 10.37236/4119
ID - 10_37236_4119
ER -
%0 Journal Article
%A Michael Albert
%A Mathilde Bouvel
%T Operators of equivalent sorting power and related Wilf-equivalences
%J The electronic journal of combinatorics
%D 2014
%V 21
%N 4
%U http://geodesic.mathdoc.fr/articles/10.37236/4119/
%R 10.37236/4119
%F 10_37236_4119
Michael Albert; Mathilde Bouvel. Operators of equivalent sorting power and related Wilf-equivalences. The electronic journal of combinatorics, Tome 21 (2014) no. 4. doi: 10.37236/4119
