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

Baxter permutationsenumerationgeneralized patternsgenerating treespermutation statisticspermutationsstack sortingsymmetries 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

• (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
• scientific article; zbMATH DE number 1178976 (Why is no real title available?)
• 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 number of Baxter permutations
• The On-Line Encyclopedia of Integer Sequences

Cited in

(16)

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

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)