Counting 3-Stack-Sortable Permutations

We prove a “decomposition lemma” that allows us to count preimages of certain sets of permutations under West’s stack-sorting map $s$. As a first application, we give a new proof of Zeilberger’s formula for the number of 2-stack-sortable permutations in $S_n$. Our proof generalizes, allowing us to find an algebraic equation satisfied by the generating function that counts 2-stack-sortable permutations according to length, number of descents, and number of peaks. The same method yields a recurrence relation for $W_3(n)$, the number of 3-stack-sortable permutations in $S_n$. We compute $W_3(n)$ for $n\le 174$, extending the 13 terms of this sequence that were known before. We also prove the first nontrivial lower bound for $\underset{n\to \mathrm{\infty }}{\lim }{W}_3(n{)}^{1\mathrm{/}n}$. Invoking a result of Kremer, we also prove that $\underset{n\to \mathrm{\infty }}{\lim }{W}_t(n{)}^{1\mathrm{/}n}\ge (\sqrt{t}+1{)}^2$ for all $t\ge 1$, which we use to improve a result of Smith. Our computations allow us to disprove a conjecture of B'ona, although we do not yet know for sure which one. We can refine our methods to obtain a recurrence for the number of 3-stack-sortable permutations in $S_n$ with $k$ descents and $p$ peaks. This produces a large amount of evidence supporting a real-rootedness conjecture of B'ona. Using part of the theory of valid hook configurations, we give a new proof of a $\gamma$-nonnegativity result of Br"and'en, which in turn implies an older result of B'ona. We then answer a question of the current author by producing a set $A\subseteq S_{11}$ such that $\sum_{\sigma\in s^{-1}(A)}x^{$\text{des}$(\sigma)}$ has nonreal roots. We interpret this as partial evidence against the same real-rootedness conjecture of B'ona that we found evidence supporting. Examining the parities of the numbers $W_3(n)$, we obtain strong evidence against yet another conjecture of B'ona. We end with some conjectures of our own.