Mathilde Bouvel ; Olivier Guibert - Enumeration of permutations sorted with two passes through a stack and D_8 symmetries

dmtcs:3080 - Discrete Mathematics & Theoretical Computer Science, January 1, 2012, DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012) - https://doi.org/10.46298/dmtcs.3080
Enumeration of permutations sorted with two passes through a stack and D_8 symmetriesConference paper

Authors: Mathilde Bouvel 1; Olivier Guibert 1

  • 1 Laboratoire Bordelais de Recherche en Informatique

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.

https://doi.org/10.46298/dmtcs.3080
Source: HAL:hal-01283130v1
Volume: DMTCS Proceedings vol. AR, 24th International Conference on Formal Power Series and Algebraic Combinatorics (FPSAC 2012)
Section: Proceedings
Published on: January 1, 2012
Imported on: January 31, 2017
Keywords: permutations, generalized patterns, stack sorting, symmetries of the square, Baxter permutations, generating trees,[INFO.INFO-DM]Computer Science [cs]/Discrete Mathematics [cs.DM]

1 Document citing this article

Share and export

Consultation statistics

This page has been seen 301 times.
This article's PDF has been downloaded 278 times.