| Summary: | 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.
|
|---|