Back to overview

Refined enumeration of permutations sorted with two stacks and a D_8-symmetry.

Type of publication Peer-reviewed
Publikationsform Original article (peer-reviewed)
Author Mathilde Bouvel, Olivier Guibert,
Project Permutation classes: from structure to combinatorial properties
Show all

Original article (peer-reviewed)

Journal Annals of Combinatorics
Volume (Issue) 18(2)
Page(s) 199 - 232
Title of proceedings Annals of Combinatorics

Open Access

Type of Open Access Repository (Green Open Access)


We study permutations that are sorted by operators of the form S.alpha.S, where S 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. Steingrimsson. 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.