Stack-Sorting Preimages of Permutation Classes

Colin Defant

Séminaire lotharingien de combinatoire, Tome 82 (2020-2021)

Résumé

We extend and generalize many of the enumerative results concerning West's stack-sorting map s. First, we prove a useful theorem that allows one to efficiently compute |s^-1(π)| for any permutation π, answering a question of Bousquet-M\'elou. This method relies on combinatorial objects called ``valid hook configurations." We then enumerate permutations in various sets of the form s^-1(Av(τ⁽¹⁾,...,τ^(r))), where Av(τ⁽¹⁾,...,τ^(r)) is the set of permutations avoiding the patterns τ⁽¹⁾,...,τ^(r). In many cases studied in this paper, these preimage sets are permutation classes themselves. In one case, we solve a problem previously posed by Bruner. We are often able to refine our counts by enumerating these permutations according to their number of descents or peaks. Our investigation not only provides several new combinatorial interpretations and identities involving known sequences, but also paves the way for several new enumerative problems.