Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
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 $s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a ne...
| Main Author: | |
|---|---|
| Format: | Article |
| Language: | English |
| Published: |
Discrete Mathematics & Theoretical Computer Science
2021-04-01
|
| Series: | Discrete Mathematics & Theoretical Computer Science |
| Subjects: | |
| Online Access: | https://dmtcs.episciences.org/6709/pdf |
| _version_ | 1797270018995519488 |
|---|---|
| author | Colin Defant |
| author_facet | Colin Defant |
| author_sort | Colin Defant |
| collection | DOAJ |
| description | 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
$s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new example
of an unbalanced Wilf equivalence. This result is equivalent to the enumeration
of permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubble
sort map. We then prove that the sets $s^{-1}(\text{Av}(231,312))$,
$s^{-1}(\text{Av}(132,231))=\text{Av}(2341,1342,\underline{32}41,\underline{31}42)$,
and $s^{-1}(\text{Av}(132,312))=\text{Av}(1342,3142,3412,34\underline{21})$ 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
$s^{-1}(\text{Av}(\tau^{(1)},\ldots,\tau^{(r)}))$ for
$\{\tau^{(1)},\ldots,\tau^{(r)}\}\subseteq S_3$ with the exception of the set
$\{321\}$. We also find an explicit formula for
$|s^{-1}(\text{Av}_{n,k}(231,312,321))|$, where $\text{Av}_{n,k}(231,312,321)$
is the set of permutations in $\text{Av}_n(231,312,321)$ with $k$ descents.
This allows us to prove a conjectured identity involving Catalan numbers and
order ideals in Young's lattice. |
| first_indexed | 2024-03-11T21:31:58Z |
| format | Article |
| id | doaj.art-99b8bc09caf44bab8bd5346b3dfadff9 |
| institution | Directory Open Access Journal |
| issn | 1365-8050 |
| language | English |
| last_indexed | 2024-04-25T01:57:36Z |
| publishDate | 2021-04-01 |
| publisher | Discrete Mathematics & Theoretical Computer Science |
| record_format | Article |
| series | Discrete Mathematics & Theoretical Computer Science |
| spelling | doaj.art-99b8bc09caf44bab8bd5346b3dfadff92024-03-07T15:41:55ZengDiscrete Mathematics & Theoretical Computer ScienceDiscrete Mathematics & Theoretical Computer Science1365-80502021-04-01vol. 22 no. 2, Permutation...Combinatorics10.46298/dmtcs.67096709Enumeration of Stack-Sorting Preimages via a Decomposition LemmaColin DefantWe 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 $s^{-1}(\text{Av}(231,321))=\text{Av}(2341,3241,45231)$, finding a new example of an unbalanced Wilf equivalence. This result is equivalent to the enumeration of permutations sortable by ${\bf B}\circ s$, where ${\bf B}$ is the bubble sort map. We then prove that the sets $s^{-1}(\text{Av}(231,312))$, $s^{-1}(\text{Av}(132,231))=\text{Av}(2341,1342,\underline{32}41,\underline{31}42)$, and $s^{-1}(\text{Av}(132,312))=\text{Av}(1342,3142,3412,34\underline{21})$ 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 $s^{-1}(\text{Av}(\tau^{(1)},\ldots,\tau^{(r)}))$ for $\{\tau^{(1)},\ldots,\tau^{(r)}\}\subseteq S_3$ with the exception of the set $\{321\}$. We also find an explicit formula for $|s^{-1}(\text{Av}_{n,k}(231,312,321))|$, where $\text{Av}_{n,k}(231,312,321)$ is the set of permutations in $\text{Av}_n(231,312,321)$ with $k$ descents. This allows us to prove a conjectured identity involving Catalan numbers and order ideals in Young's lattice.https://dmtcs.episciences.org/6709/pdfmathematics - combinatorics05a05, 05a15 |
| spellingShingle | Colin Defant Enumeration of Stack-Sorting Preimages via a Decomposition Lemma Discrete Mathematics & Theoretical Computer Science mathematics - combinatorics 05a05, 05a15 |
| title | Enumeration of Stack-Sorting Preimages via a Decomposition Lemma |
| title_full | Enumeration of Stack-Sorting Preimages via a Decomposition Lemma |
| title_fullStr | Enumeration of Stack-Sorting Preimages via a Decomposition Lemma |
| title_full_unstemmed | Enumeration of Stack-Sorting Preimages via a Decomposition Lemma |
| title_short | Enumeration of Stack-Sorting Preimages via a Decomposition Lemma |
| title_sort | enumeration of stack sorting preimages via a decomposition lemma |
| topic | mathematics - combinatorics 05a05, 05a15 |
| url | https://dmtcs.episciences.org/6709/pdf |
| work_keys_str_mv | AT colindefant enumerationofstacksortingpreimagesviaadecompositionlemma |