Séminaire Lotharingien de Combinatoire, B82b (2020), 41 pp.
Colin Defant
Stack-Sorting Preimages of Permutation Classes
Abstract.
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(τ(1),...,τ(r))), where
Av(τ(1),...,τ(r)) is the set of permutations
avoiding the patterns τ(1),...,τ(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.
Received: April 12, 2019.
Revised: December 17, 2019.
Accepted: March 21, 2020.
The following versions are available: