
arXiv: 1402.2034
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.
FOS: Computer and information sciences, Permutations, words, matrices, Wilf-equivalence, Discrete Mathematics (cs.DM), wilf-equivalence, stack, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Combinatorics in computer science, permutation, enumeration, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], bijection, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, sorting, Combinatorial identities, bijective combinatorics, Computer Science - Discrete Mathematics
FOS: Computer and information sciences, Permutations, words, matrices, Wilf-equivalence, Discrete Mathematics (cs.DM), wilf-equivalence, stack, [info.info-dm] computer science [cs]/discrete mathematics [cs.dm], Combinatorics in computer science, permutation, enumeration, [INFO.INFO-DM] Computer Science [cs]/Discrete Mathematics [cs.DM], bijection, QA1-939, FOS: Mathematics, Mathematics - Combinatorics, Combinatorics (math.CO), Mathematics, sorting, Combinatorial identities, bijective combinatorics, Computer Science - Discrete Mathematics
| selected citations These citations are derived from selected sources. This is an alternative to the "Influence" indicator, which also reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | 2 | |
| popularity This indicator reflects the "current" impact/attention (the "hype") of an article in the research community at large, based on the underlying citation network. | Average | |
| influence This indicator reflects the overall/total impact of an article in the research community at large, based on the underlying citation network (diachronically). | Top 10% | |
| impulse This indicator reflects the initial momentum of an article directly after its publication, based on the underlying citation network. | Average |
