Refined enumeration of permutations sorted with two stacks and a D₈-symmetry

DOI10.1007/S00026-014-0219-8MaRDI QIDQ404464zbMATH OpenOpenAlexFDO

Authors Mathilde Bouvel, Olivier Guibert

Publication date 4 September 2014

Published in Annals of Combinatorics (Search for Journal in Brave)

Full work available at URL https://arxiv.org/abs/1210.5967

zbMATH Keywords

permutationsenumerationstack sortingpermutation statisticsgenerating treesBaxter permutationsgeneralized patternssymmetries of the square

Mathematics Subject Classification ID

Permutations, words, matrices (05A05) Exact enumeration problems, generating functions (05A15)

Abstract: We study permutations that are sorted by operators of the form $mathbfScircalphacircmathbfS$, where $mathbfS$ is the usual stack sorting operator introduced by D. Knuth and $alpha$ is any $D_8$-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.

Recommendations

• Enumeration of permutations sorted with two passes through a stack and \(D_{8}\) symmetries
• Stack-sortable permutations and beyond
• Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture
• Permutations sortable by two stacks in parallel and quarter plane walks
• Operators of equivalent sorting power and related Wilf-equivalences

Cites work

• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• (2+2)-free posets, ascent sequences and pattern avoiding permutations
• A combinatorial proof of J. West's conjecture
• 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)\)!)
• A survey of stack-sorting disciplines
• A unification of permutation patterns related to Schubert varieties
• Algebraic and combinatorial structures on pairs of twin binary trees
• Baxter permutations
• Describing West-3-stack-sortable permutations with permutation patterns
• ECO:a methodology for the enumeration of combinatorial objects
• Enumerating permutations avoiding three Babson-Steingrímsson patterns
• Generalized permutation patterns and a classification of the Mahonian statistics
• Generating trees and the Catalan and Schröder numbers
• Mesh patterns and the expansion of permutation statistics as sums of permutation patterns
• Multi-static enumeration of two-stack sortable permutations
• On Fixed Points of the Composite of Commuting Functions
• On the inverse image of pattern classes under bubble sort
• Permutation patterns and statistics
• Permutations ayant une forme donnée
• Permutations sortable by \(n - 4\) passes through a stack
• Permutations with forbidden subsequences and nonseparable planar maps
• Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
• Sorted and/or sortable permutations
• Sorting and preimages of pattern classes
• Sorting twice through a stack
• The On-Line Encyclopedia of Integer Sequences
• The number of Baxter permutations

Cited in

(16)

• Revstack sort, zigzag patterns, descent polynomials of \(t\)-revstack sortable permutations, and Steingrímsson's sorting conjecture
• Fertility, Strong Fertility, and Postorder Wilf Equivalence
• Semi-Baxter and strong-Baxter: two relatives of the Baxter sequence
• Vincular pattern avoidance on cyclic permutations
• Tableau sequences, open diagrams, and Baxter families
• Slicings of parallelogram polyominoes, or how Baxter and Schröder can be reconciled
• Pattern-avoiding inversion sequences and open partition diagrams
• Enumeration of permutations sorted with two passes through a stack and \(D_{8}\) symmetries
• Semi-Baxter and strong-Baxter permutations
• Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
• A generating tree approach to \(k\)-nonnesting partitions and permutations
• Counting 3-stack-sortable permutations
• Stack-sorting preimages of permutation classes
• Polyurethane toggles
• Slicings of parallelogram polyominoes: Catalan, Schröder, Baxter, and other sequences
• Operators of equivalent sorting power and related Wilf-equivalences

Describes a project that uses

Uses Software

• OEIS

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)