Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
From MaRDI portal
Publication:404464
DOI10.1007/S00026-014-0219-8zbMATH Open1295.05009arXiv1210.5967OpenAlexW2092556779MaRDI QIDQ404464FDOQ404464
Mathilde Bouvel, Olivier Guibert
Publication date: 4 September 2014
Published in: Annals of Combinatorics (Search for Journal in Brave)
Abstract: We study permutations that are sorted by operators of the form , where is the usual stack sorting operator introduced by D. Knuth and is any -symmetry obtained combining the classical reverse, complement and inverse operations. Such permutations can be characterized by excluded (generalized) patterns. Some conjectures about the enumeration of these permutations, refined with numerous classical statistics, have been proposed by A. Claesson, M. Dukes and E. Steingr'imsson. We prove these conjectures, and enrich one of them with a few more statistics. The proofs mostly rely on generating trees techniques, and on a recent bijection of S. Giraudo between Baxter and twisted Baxter permutations.
Full work available at URL: https://arxiv.org/abs/1210.5967
permutationsenumerationstack sortingpermutation statisticsgenerating treesBaxter permutationsgeneralized patternssymmetries of the square
Cites Work
- Title not available (Why is that?)
- The On-Line Encyclopedia of Integer Sequences
- Generalized permutation patterns and a classification of the Mahonian statistics
- Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
- Generating trees and the Catalan and Schröder numbers
- Permutation patterns and statistics
- A survey of stack-sorting disciplines
- ECO:a methodology for the enumeration of combinatorial objects
- The number of Baxter permutations
- (2+2)-free posets, ascent sequences and pattern avoiding permutations
- Permutations ayant une forme donnée
- Describing West-3-stack-sortable permutations with permutation patterns
- Enumerating permutations avoiding three Babson-Steingrímsson patterns
- 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)\)!)
- Multi-static enumeration of two-stack sortable permutations
- A combinatorial proof of J. West's conjecture
- Sorted and/or sortable permutations
- Algebraic and combinatorial structures on pairs of twin binary trees
- Permutations with forbidden subsequences and nonseparable planar maps
- Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
- A unification of permutation patterns related to Schubert varieties
- On the inverse image of pattern classes under bubble sort
- On Fixed Points of the Composite of Commuting Functions
- Sorting and preimages of pattern classes
- Baxter permutations
- Permutations sortable by \(n - 4\) passes through a stack
- Sorting twice through a stack
Cited In (14)
- Counting 3-stack-sortable permutations
- Title not available (Why is that?)
- Pattern-avoiding inversion sequences and open partition diagrams
- Semi-Baxter and strong-Baxter permutations
- Vincular pattern avoidance on cyclic permutations
- Revstack sort, zigzag patterns, descent polynomials of \(t\)-revstack sortable permutations, and Steingrímsson's sorting conjecture
- Polyurethane toggles
- Semi-Baxter and Strong-Baxter: Two Relatives of the Baxter Sequence
- Fertility, Strong Fertility, and Postorder Wilf Equivalence
- A generating tree approach to \(k\)-nonnesting partitions and permutations
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Tableau sequences, open diagrams, and Baxter families
- Stack-sorting preimages of permutation classes
- Slicings of parallelogram polyominoes: Catalan, Schröder, Baxter, and other sequences
Uses Software
This page was built for publication: Refined enumeration of permutations sorted with two stacks and a \(D_8\)-symmetry
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q404464)
