Operators of equivalent sorting power and related Wilf-equivalences
type: Item
instance of: scholarly article
title: Operators of equivalent sorting power and related Wilf-equivalences
zbMATH Open document ID: 1298.05005
author: Mathilde Bouvel
author: Michael Albert
published in: The Electronic Journal of Combinatorics
publication date: 2014-10-23T00:00:00Z
full work available at URL: v21i4p11
review text: Summary: 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.
Mathematics Subject Classification ID: 05A05
Mathematics Subject Classification ID: 05A19
Mathematics Subject Classification ID: 68R05
zbMATH DE Number: 6360686
zbMATH Keywords: permutation
zbMATH Keywords: stack
zbMATH Keywords: sorting
zbMATH Keywords: enumeration
zbMATH Keywords: bijection
zbMATH Keywords: Wilf-equivalence
MaRDI profile type: Publication
cites work: Simple permutations and pattern restricted permutations
cites work: Operators of equivalent sorting power and related Wilf-equivalences
cites work: A general theory of Wilf-equivalence for Catalan structures
cites work: Pattern matching for permutations
cites work: Sorted and/or sortable permutations
cites work: Q5377425
cites work: Classification of bijections between 321- and 132-avoiding permutations
cites work: Sorting and preimages of pattern classes
cites work: Permutation patterns and statistics
cites work: Patterns in permutations and words.
cites work: Q5585021
cites work: Restricted 132-avoiding permutations
cites work: Restricted permutations, continued fractions, and Chebyshev polynomials
cites work: Q4074820
cites work: Restricted permutations
cites work: Sorting Using Networks of Queues and Stacks
cites work: Describing West-3-stack-sortable permutations with permutation patterns
cites work: Sorting twice through a stack
cites work: A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
description: scientific article; zbMATH DE number 6360686