Enumeration of permutations sorted with two passes through a stack and D_8 symmetries

Abstract

We examine the sets of permutations that are sorted by two passes through a stack with a $D_8$ operation performed in between. From a characterization of these in terms of generalized excluded patterns, we prove two conjectures on their enumeration, that can be refined with the distribution of some statistics. The results are obtained by generating trees.

Keywords

• baxter permutations
• generating trees
• permutations
• generalized patterns
• stack sorting
• symmetries of the square
• [info.info-dm] computer science [cs]/discrete mathematics [cs.dm]