Processing math: 100%

Colin Defant - Enumeration of Stack-Sorting Preimages via a Decomposition Lemma

dmtcs:6709 - Discrete Mathematics & Theoretical Computer Science, April 9, 2021, vol. 22 no. 2, Permutation Patterns 2019 - https://doi.org/10.46298/dmtcs.6709
Enumeration of Stack-Sorting Preimages via a Decomposition LemmaArticle

Authors: Colin Defant

    We give three applications of a recently-proven "Decomposition Lemma," which allows one to count preimages of certain sets of permutations under West's stack-sorting map s. We first enumerate the permutation class s1(Av(231,321))=Av(2341,3241,45231), finding a new example of an unbalanced Wilf equivalence. This result is equivalent to the enumeration of permutations sortable by Bs, where B is the bubble sort map. We then prove that the sets s1(Av(231,312)), s1(Av(132,231))=Av(2341,1342,32_41,31_42), and s1(Av(132,312))=Av(1342,3142,3412,3421_) are counted by the so-called "Boolean-Catalan numbers," settling a conjecture of the current author and another conjecture of Hossain. This completes the enumerations of all sets of the form s1(Av(τ(1),,τ(r))) for {τ(1),,τ(r)}S3 with the exception of the set {321}. We also find an explicit formula for |s1(Avn,k(231,312,321))|, where Avn,k(231,312,321) is the set of permutations in Avn(231,312,321) with k descents. This allows us to prove a conjectured identity involving Catalan numbers and order ideals in Young's lattice.


    Volume: vol. 22 no. 2, Permutation Patterns 2019
    Section: Combinatorics
    Published on: April 9, 2021
    Accepted on: March 23, 2021
    Submitted on: August 12, 2020
    Keywords: Mathematics - Combinatorics,05A05, 05A15

    1 Document citing this article

    Consultation statistics

    This page has been seen 647 times.
    This article's PDF has been downloaded 318 times.