Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
arXiv:1904.02829 · doi:10.46298/dmtcs.6709
Abstract
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 . We first enumerate the permutation class , finding a new example of an unbalanced Wilf equivalence. This result is equivalent to the enumeration of permutations sortable by , where is the bubble sort map. We then prove that the sets , , and 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 for with the exception of the set . We also find an explicit formula for , where is the set of permutations in with descents. This allows us to prove a conjectured identity involving Catalan numbers and order ideals in Young's lattice.
arXiv comment20 pages, 4 figures. arXiv admin note: text overlap with arXiv:1903.09138
References in corpus (9)
- Actions on permutations and unimodality of descent polynomials
- Describing West-3-stack-sortable permutations with permutation patterns
- Lattice Paths and Pattern-Avoiding Uniquely Sorted Permutations
- Stack-Sorting Preimages of Permutation Classes
- Egge triples and unbalanced Wilf-equivalence
- Fighting fish and two-stack sortable permutations
- Permutations avoiding 4321 and 3241 have an algebraic generating function
- Stack-sorting for Words
- A stack and a pop stack in series