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.
Categories: math.CO