Enumeration of permutations sorted with two passes through a stack and D8 symmetries
Mathilde Bouvel, Olivier Guibert
Abstract
We examine the sets of permutations that are sorted by two passes through a stack with a D8 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.
Résumé. On étudie les ensembles de permutations qui sont triées par deux passages dans une pile séparés par une opération du groupe D8. À partir d'une caractérisation de ces ensembles en termes de motifs exclus généralisés, on démontre deux conjectures sur leur énumération, qui peuvent être raffinées par la distribution de certaines statistiques. Ces résultats sont obtenus à l'aide d'arbres de génération.
Résumé. On étudie les ensembles de permutations qui sont triées par deux passages dans une pile séparés par une opération du groupe D8. À partir d'une caractérisation de ces ensembles en termes de motifs exclus généralisés, on démontre deux conjectures sur leur énumération, qui peuvent être raffinées par la distribution de certaines statistiques. Ces résultats sont obtenus à l'aide d'arbres de génération.
Full Text: PostScript PDF