\documentclass[finalversion]{FPSAC2021}
\articlenumber{7}

\usepackage{tabu}
\usepackage{makecell}


\newtheorem{theorem}{Theorem}[section]
\newtheorem{lemma}[theorem]{Lemma}
\newtheorem{corollary}[theorem]{Corollary}
\newtheorem{conjecture}[theorem]{Conjecture}

\theoremstyle{definition}
\newtheorem{definition}[theorem]{Definition}
\newtheorem{example}[theorem]{Example}

\DeclareMathOperator{\des}{des}
\DeclareMathOperator{\peak}{peak}
\DeclareMathOperator{\Av}{Av}
\DeclareMathOperator{\SW}{SW}
\DeclareMathOperator{\tl}{tl}
\DeclareMathOperator{\leg}{leg}




\title[$3$-Stack-Sortable Permutations and Beyond]{$3$-Stack-Sortable Permutations and Beyond}

\author{Colin Defant\thanks{\href{mailto:cdefant@princeton.edu}{cdefant@princeton.edu}. The author was supported by a Fannie and John Hertz Foundation Fellowship and an NSF Graduate Research Fellowship.}\addressmark{1}}


\address{\addressmark{1}Department of Mathematics, Princeton University, Princeton, NJ}

\received{11/13/2020}


%\revised{}

\abstract{We state a Decomposition Lemma that allows us to count preimages of permutations under West's stack-sorting map. This result and its generalizations have several applications to the study of stack-sorting and beyond; we will explicate two of these applications and state the remaining ones without details. First, we give a new proof of Zeilberger's formula for the number $W_2(n)$ of $2$-stack-sortable permutations in $S_n$. We then obtain a polynomial-time algorithm for counting $3$-stack-sortable permutations, settling a 30-year-old open problem. This algorithm allows us to prove the first nontrivial lower bound for $\lim\limits_{n\to\infty}W_3(n)^{1/n}$ and to disprove a conjecture of B\'ona. We also use new data obtained from the algorithm to comment on two of B\'ona's other conjectures. Finally, we prove that $\lim\limits_{n\to\infty}W_t(n)^{1/n}\geq(\sqrt{t}+1)^2$ for all $t\geq 1$, allowing us to improve a result of Smith concerning a variant of the stack-sorting procedure. }

\keywords{permutation, stack-sorting, pattern avoidance, troupe}

\usepackage[backend=bibtex]{biblatex}
\addbibresource{07Defant.bib}

\renewbibmacro{in:}{}


\begin{document}

\maketitle

\section{Introduction}
In this article, a \emph{permutation} is an ordering of a set of positive integers written in one-line notation. Let $S_n$ denote the set of permutations of the set $[n]$. If $\pi$ is a permutation of size $n$, then the \emph{standardization} of $\pi$ is the permutation in $S_n$ obtained by replacing the $i^\text{th}$-smallest entry in $\pi$ with $i$ for all $i\in[n]$. For example, the standardization of $3614$ is $2413$. Given permutations $\pi$ and $\tau$, we say $\pi$ \emph{contains} $\tau$ if there is a (not necessarily consecutive) subsequence of $\pi$ whose standardization is the same as the standardization of $\tau$; otherwise, we say $\pi$ \emph{avoids} $\tau$. A \emph{descent} of a permutation $\pi=\pi_1\cdots\pi_n$ is an index $i\in[n-1]$ such that $\pi_i>\pi_{i+1}$. A \emph{peak} of $\pi$ is an index $i\in\{2,\ldots,n-1\}$ such that $\pi_{i-1}<\pi_i>\pi_{i+1}$. Let $\des(\pi)$ and $\peak(\pi)$ denote the number of descents of $\pi$ and the number of peaks of $\pi$, respectively. 

The study of permutation patterns began with Knuth's analysis of a certain stack-sorting machine \cite{Knuth}. In his dissertation, West \cite{West} defined a deterministic variant of Knuth's machine, which is a function that we denote by $s$ and define as follows. First, $s$ sends the empty permutation to itself. Given a nonempty permutation $\pi$ with largest entry $m$, we can write $\pi=LmR$ for some permutations $L$ and $R$. Then $s(\pi)=s(L)s(R)m$. For example,
$s(3521764)=s(3521)\,s(64)7=s(3)\,s(21)5\,s(4)67=3\,s(1)25467=3125467$.

\begin{definition}\label{Def1}
We say a permutation $\pi$ is $t$-\emph{stack-sortable} if $s^t(\pi)$ is an increasing permutation, where $s^t$ denotes the $t$-fold iterate of $s$. Let $\mathcal W_t(n)$ be the set of $t$-stack-sortable permutations in $S_n$, and let $W_t(n)=|\mathcal W_t(n)|$. 
\end{definition}

The next theorem follows from Knuth's analysis of his stack-sorting machine. 
\begin{theorem}[\cite{Knuth}]\label{Thm1}
A permutation is $1$-stack-sortable if and only if it avoids the pattern $231$. Furthermore, $W_1(n)=C_n:=\frac{1}{n+1}{2n\choose n}$ is the $n^\text{th}$ Catalan number.
\end{theorem}

West \cite{West} conjectured, and Zeilberger \cite{Zeilberger} later proved, that $W_2(n)=\frac{2}{(n+1)(2n+1)}\binom{3n}{n}$; there have now been several articles devoted to finding new proofs and extensions of this formula (see the references in \cite{DefantCounting}). 

Until recently, there was very little known about $3$-stack-sortable permutations. \'Ulfarsson \cite{Ulfarsson} characterized $3$-stack-sortable permutations in terms of new ``decorated patterns,'' but the characterization is too unwieldy to yield any additional information. In \cite{DefantPreimages}, the current author initiated the theory of combinatorial objects called ``valid hook configurations'' and used these objects to prove the estimates $\lim\limits_{n\to\infty}W_3(n)^{1/n}<12.53296$ and $\lim\limits_{n\to\infty}W_4(n)^{1/n}<21.97225$.
Ever since West wrote his dissertation in 1990, one of the largest unsolved problems in the theory of the stack-sorting map has been to find a polynomial-time algorithm for computing the numbers $W_3(n)$. This extended abstract is primarily based on the article \cite{DefantCounting}, which finds a recurrence that settles this problem. 

The key result that we will need is the Decomposition Lemma, which gives a recursive method for computing $|s^{-1}(\pi)|$ for any permutation $\pi$. There are far-reaching applications and generalizations of the Decomposition Lemma that even extend beyond the realm of stack-sorting. We will briefly mention some of these applications, but due to space limitations, the only applications for which we provide details are a new proof of Zeilberger's formula for $W_2(n)$ and the proof of the recurrence for $W_3(n)$. 

\section{The Decomposition Lemma}\label{Sec:DecompLemma}

The \emph{plot} of a permutation $\pi=\pi_1\cdots\pi_n$ is the diagram showing the points $(i,\pi_i)\in\mathbb R^2$ for all $1\leq i\leq n$. A \emph{hook} of $\pi$ is a rotated L shape connecting two points $(i,\pi_i)$ and $(j,\pi_j)$ with $i<j$ and $\pi_i<\pi_j$, as in Figure~\ref{Fig4}. The point $(i,\pi_i)$ is the \emph{southwest endpoint} of the hook, and $(j,\pi_j)$ is the \emph{northeast endpoint} of the hook. Let $\SW_i(\pi)$ be the set of hooks of $\pi$ with southwest endpoint $(i,\pi_i)$. For example, Figure~\ref{Fig4} shows the plot of the permutation $\pi=426315789$. The hook shown in this figure is in $\SW_3(\pi)$ because its southwest endpoint is $(3,6)$; its northeast endpoint is $(8,8)$. 

\begin{figure}[ht]
  \begin{center}{\includegraphics[width=0.22\textwidth]{ThesisPIC4}}
  \end{center}
  \caption{The plot of $426315789$ along with a single hook.}\label{Fig4}
\end{figure}

Suppose $\pi=\pi_1\cdots\pi_n$ is not a monotone increasing permutation, and let $d^*$ be its largest descent. We say a descent $d$ of $\pi$ is \emph{right-bound} if $\pi_j<\pi_d$ for all $j\in\{d+1,\ldots,d^*\}$ (in particular, $d^*$ is right-bound). The descents of $426315789$ are $1$, $3$, and $4$, but the only right-bound descents are $3$ and $4$. 

Let $H$ be a hook of $\pi$ with southwest endpoint $(i,\pi_i)$ and northeast endpoint $(j,\pi_j)$. The \emph{$H$-unsheltered subpermutation of $\pi$} is the permutation $\pi_U^H=\pi_1\cdots\pi_i\pi_{j+1}\cdots\pi_n$. The \emph{$H$-sheltered subpermutation of $\pi$} is $\pi_S^H=\pi_{i+1}\cdots\pi_{j-1}$. For instance, if $\pi=426315789$ and $H$ is the hook shown in Figure~\ref{Fig4}, then $\pi_U^H=4269$ and $\pi_S^H=3157$. The terms ``sheltered'' and ``unsheltered'' come from the fact that, in applications, the plot of $\pi_S^H$ will lie entirely below the hook $H$. In particular, this will be the case if $i$ is a right-bound descent of $\pi$.  

Notice that if $\pi$ does not have any right-bound descents, then $\pi$ is an increasing permutation and $|s^{-1}(\pi)|$ is simply a Catalan number by Theorem~\ref{Thm1}.

\begin{theorem}[Decomposition Lemma \cite{DefantCounting}]\label{Cor1}
If $d$ is a right-bound descent of a permutation $\pi$, then \[|s^{-1}(\pi)|=\sum_{H\in\SW_d(\pi)}|s^{-1}(\pi_U^H)|\cdot|s^{-1}(\pi_S^H)|.\]
\end{theorem}

The Decomposition Lemma is proven in \cite{DefantCounting}.\footnote{The statement in \cite{DefantCounting} uses the less general ``tail-bound descents'' instead of right-bound descents, but the same proof adapts easily to the more general setting. In any event, the version involving right-bound descents follows from a much more general result proven in \cite{DefantTroupes}.} 

\begin{example}
Let $\pi=256341789$. Using the Decomposition Lemma with the right-bound descent $d=3$ (see Figure~\ref{Fig2}), we find that \[|s^{-1}(\pi)|=\sum_{H\in\SW_3(\pi)}|s^{-1}(\pi_U^H)|\cdot|s^{-1}(\pi_S^H)|\] \[=|s^{-1}(25689)|\cdot|s^{-1}(341)|+|s^{-1}(2569)|\cdot|s^{-1}(3417)|+|s^{-1}(256)|\cdot|s^{-1}(34178)|\] \[=42\cdot 0+14\cdot 2+5\cdot 9=73.\] Indeed, it follows from Theorem~\ref{Thm1} that $|s^{-1}(\sigma)|=C_m=\frac{1}{m+1}\binom{2m}{m}$ whenever $\sigma$ is an increasing permutation of size $m$. One can use further applications of the Decomposition Lemma to see that $|s^{-1}(341)|=0$, $|s^{-1}(3417)|=2$ and $|s^{-1}(34178)|=9$. 


\begin{figure}[h]
  \begin{center}{\includegraphics[width=0.75\textwidth]{3StackPIC3New}}
  \end{center}
  \caption{Three different decompositions of $256341789$. For each of the hooks $H$ in $\SW_3(\pi)$, the $H$-unsheltered subpermutation of $\pi$ is represented by blue squares, while the $H$-sheltered subpermutation of $\pi$ is represented by red triangles.}\label{Fig2}
\end{figure}
\end{example}

We briefly list some of the extensions and applications of the Decomposition Lemma. 


\begin{enumerate}
    \item In \cite{DefantTroupes}, the author has proven a result called the Tree Decomposition Lemma. This is a vast generalization of the Decomposition Lemma that yields information about sets of colored binary plane trees called ``troupes.'' For any permutation $\pi$, this result gives a method to count the decreasing colored binary plane trees whose underlying unlabeled trees belong to a specified troupe and whose postorder readings are $\pi$. The Tree Decomposition Lemma is even further generalized to the Refined Tree Decomposition Lemma, which takes into account special ``insertion-additive'' tree statistics. By specializing the Refined Tree Decomposition Lemma, one can count $2$-stack-sortable permutations and $3$-stack-sortable permutations according to their descent and peak statistics; even for $2$-stack-sortable permutations, this is a new result that appeared originally in \cite{DefantCounting}. One can also enumerate $2$-stack-sortable permutations and $3$-stack-sortable permutations satisfying certain additional conditions. For example, one can impose the condition that the permutations are alternating and of odd size. As another example, one can impose the condition that all of the descents of the permutations are also peaks. All of these results can be proved in a uniform manner from the Refined Tree Decomposition Lemma. 
    \item The article \cite{DefantTroupes} details an intimate connection between stack-sorting and cumulants in noncommutative probability theory. This connection allows one to use the combinatorics of cumulants in order to derive deep results about stack-sorting. On the other hand, there is a surprising phenomenon concerning troupes and cumulants (but not stated in terms of stack-sorting) that can be proved using stack-sorting (and its generalizations) as a tool. The first step needed to establish these connections is the Refined Tree Decomposition Lemma. 
    \item As shown in \cite{DefantTroupes}, one can iterate the Decomposition Lemma in order to obtain a clean proof of a Fertility Formula, which is an explicit formula for the number of preimages of a permutation under the stack-sorting map. This Fertility Formula makes use of combinatorial objects called ``valid hook configurations.'' The author has employed this formula to prove numerous new theorems about stack-sorting (see the references in \cite{DefantCounting,DefantTroupes}), uncovering much unexpected enumerative structure. 
    \item In \cite{DefantMonotonicity}, the Decomposition Lemma is used to prove the ``fertility monotonicity'' theorem, which states that $|s^{-1}(\sigma)|\leq |s^{-1}(s(\sigma))|$ for every permutation $\sigma$. This theorem represents the first step toward a law-of-diminishing-returns philosophy for the stack-sorting map that B\'ona has proposed.
    \item In \cite{DefantEnumeration}, the Decomposition Lemma is used to enumerate preimages of various permutation classes under the stack-sorting map. These results provide a new example of an unbalanced Wilf equivalence, settle a conjecture of Hossain, and allow one to enumerate permutations sortable via a composition of the stack-sorting map with either the bubble sort map or the deterministic pop-stack-sorting map. 
\end{enumerate}

\section{A New Proof of the Formula for $W_2(n)$}\label{Sec:2-Stack} 

Our goal in this section is to give a new proof of the formula $W_2(n)=\frac{2}{(n+1)(2n+1)}\binom{3n}{n}$, which was originally proved by Zeilberger in \cite{Zeilberger}. Define the \emph{tail length} of a permutation $\pi=\pi_1\ldots\pi_n\in S_n$, denoted $\tl(\pi)$, to be the smallest integer $\ell\in\{0,\ldots,n\}$ such that $\pi_{i}=i$ for all $i\in\{n-\ell+1,\ldots,n\}$. For example, we have $\tl(31245)=2$, $\tl(31254)=0$, and $\tl(12345)=5$. Let \[\mathcal D_\ell(n)=\{\pi\in\mathcal W_1(n+\ell):\tl(\pi)=\ell\}\quad\mathcal D_{\geq\ell}(n)=\{\pi\in\mathcal W_1(n+\ell):\tl(\pi)\geq\ell\},\] \[B_\ell(n)=|s^{-1}(\mathcal D_\ell(n))|,\quad\text{and}\quad B_{\geq \ell}(n)=|s^{-1}(\mathcal D_{\geq \ell}(n))|.\] Recall also that $\mathcal W_1(m)$ is the set of $231$-avoiding permutations in $S_m$ by Theorem~\ref{Thm1}.  

Suppose $\pi\in\mathcal D_\ell(n+1)$ is such that $\pi_{n+1-i}=n+1$ (where $n\geq 0$). Then $n+1-i$ is a right-bound descent of $\pi$. 
The Decomposition Lemma (Theorem~\ref{Cor1}) tells us that $|s^{-1}(\pi)|$ is equal to the number of triples $(H,\mu,\lambda)$, where $H\in\SW_{n+1-i}(\pi)$, $\mu\in s^{-1}(\pi_U^H)$, and $\lambda\in s^{-1}(\pi_S^H)$. Choosing $H$ amounts to choosing the number $j\in\{1,\ldots,\ell\}$ such that the northeast endpoint of $H$ is $(n+1+j,n+1+j)$. The permutation $\pi$ and the choice of $H$ determine the permutations $\pi_U^H$ and $\pi_S^H$. On the other hand, the choices of $H$ and the permutations $\pi_U^H$ and $\pi_S^H$ uniquely determine $\pi$. It follows that $B_\ell(n+1)$, which is the number of ways to choose an element of $s^{-1}(\mathcal D_\ell(n+1))$, is also the number of ways to choose $j$, the permutations $\pi_U^H$ and $\pi_S^H$, and the permutations $\mu$ and $\lambda$. Fix a choice of $j$. 

Because $\pi$ avoids $231$, we know that $\pi_U^H$ and $\pi_S^H$ are permutations of the sets \[\{1,\ldots,n-i\}\cup\{n+1\}\cup\{n+2+j,\ldots,n+\ell+1\}\quad\text{and}\quad\{n-i+1,\ldots,n+j\}\setminus\{n+1\},\] respectively. Therefore, choosing $\pi_U^H$ and $\pi_S^H$ is equivalent to choosing their standardizations. The standardization of $\pi_U^H$ is in $\mathcal D_{\geq \ell-j+1}(n-i)$, while the standardization of $\pi_S^H$ is in $\mathcal D_{\geq j-1}(i)$ (see Figure \ref{Fig1}). Any element of $\mathcal D_{\geq \ell-j+1}(n-i)$ can be chosen as the standardization of $\pi_U^H$, and any element of $\mathcal D_{\geq j-1}(i)$ can be chosen as the standardization of $\pi_S^H$. Also, $\pi_U^H$ and $\pi_S^H$ each have the same number of preimages under $s$ as their standardizations. Combining these facts, we find that the number of choices for $\pi_U^H$ and $\mu$ is $|s^{-1}(\mathcal D_{\geq \ell-j+1}(n-i))|=B_{\geq \ell-j+1}(n-i)$. Similarly, the number of choices for $\pi_S^H$ and $\lambda$ is $B_{\geq j-1}(i)$. Hence, 
\begin{equation}\label{Eq3}
B_\ell(n+1)=\sum_{i=1}^n\sum_{j=1}^\ell B_{\geq \ell-j+1}(n-i)B_{\geq j-1}(i).
\end{equation}

\begin{figure}[h]
\begin{center}
\includegraphics[width=.4\linewidth]{3StackPIC1}
\caption{The decomposition of $\pi$ into $\pi_U^H$ and $\pi_S^H$.}
\label{Fig1}
\end{center}  
\end{figure}

The recurrence \eqref{Eq3} contains the key combinatorial information needed to prove the formula for $W_2(n)$. The remainder of the proof amounts to a careful manipulation of generating functions, which we will only sketch. The details of these computations can be found in \cite{DefantCounting}. 

Let \[G_\ell(w)=\sum_{n\geq 0}B_{\geq\ell}(n)w^n\quad\text{and}\quad I(w,z)=\sum_{\ell\geq 0}G_\ell(w)z^\ell.\] Let $C(z)=\sum_{n\geq 0}C_nz^n=\dfrac{1-\sqrt{1-4z}}{2z}$ be the generating function of the Catalan numbers. Because $B_{\geq 0}(n)=W_2(n)$ is the total number of $2$-stack-sortable permutations in $S_n$, we are primarily interested in the generating function \[I(w,0)=G_0(w)=\sum_{n\geq 0}B_{\geq 0}(n)w^n=\sum_{n\geq 0}W_2(n)w^n.\] In \cite{DefantCounting}, the equation \eqref{Eq3} is used to derive the identity 
\begin{equation}\label{Eq6}
(I(w,z)-I(w,0))(I(w,z)-C(z))=\frac{I(w,z)-C(z)}{w}-\frac{I(w,z)-I(w,0)}{z}.
\end{equation}
In \cite{Bousquet}, Bousquet-M\'elou and Jehanne developed a powerful method to handle functional equations such as the one in \eqref{Eq6}; this method is employed in \cite{DefantCounting} to show that $R(I(w,0),w)=0$, where \[R(v,w)=-1 + 11 w + w^2 + v^3 w^2 + v^2 w (2 + 3 w) + v (1 - 14 w + 3 w^2).\] 
We now consider the power series $U(w)$ defined by $U(w)=w(1+U(w))^3$. One can verify that $R(1+U(w)-U(w)^2,w)=0$ and deduce that $I(w,0)=1+U(w)-U(w)^2$. Lagrange inversion then completes the proof that \[I(w,0)=\sum_{n\geq 0}\frac{2}{(n+1)(2n+1)}{3n\choose n}w^n.\] 

As mentioned in the previous section, there are much more general versions of the Decomposition Lemma, including one that takes into account the descent and peak statistics. In \cite{DefantCounting}, this generalization was used to find an explicit polynomial $R(v,w,x,y)$ such that $R(I_{x,y}(w,0),w,x,y)=0$, where \[I_{x,y}(w,0)=\sum_{n\geq 0}\sum_{\sigma\in\mathcal W_2(n)}w^nx^{\des(\sigma)+1}y^{\peak(\sigma)+1}.\] In \cite{DefantTroupes}, the author used the Refined Tree Decomposition Lemma (with only a slight modification of the argument used above) to enumerate $2$-stack-sortable alternating permutations of odd size and $2$-stack-sortable permutations in which every descent is a peak. 

\section{$3$-Stack-Sortable Permutations}\label{Sec:3-Stack} 

In the previous section, we counted $2$-stack-sortable permutations by viewing them as preimages of $231$-avoiding (i.e., $1$-stack-sortable) permutations under the stack-sorting map. In doing so, we had to keep track of the tail lengths of the $231$-avoiding permutations under consideration. In this section, we count $3$-stack-sortable permutations by viewing them as preimages of $2$-stack-sortable permutations. We will again keep track of tail lengths, but we will also need an additional new statistic. 
Given $\pi=\pi_1\cdots\pi_n\in S_n$ and $a\in\{0,\ldots,n\}$, we say the open interval $(a,a+1)$ is a \emph{legal space for $\pi$} if there do not exist indices $i_1<i_2<i_3$ such that $\pi_{i_3}\leq a<\pi_{i_1}<\pi_{i_2}$. Let $\leg(\pi)$ be the number of legal spaces of $\pi$.  

For example, if $\pi\in S_n$, then $\leg(\pi)=n+1$ if and only if $\pi$ avoids $231$. The legal spaces of $145326$ are $(0,1),(1,2),(4,5),(5,6),(6,7)$, so $\leg(145326)=5$. Imagine taking the plot of a permutation $\pi$ and adding a new point to the left of all other points. One can think of the legal spaces of $\pi$ as the vertical positions where the new point can be inserted so as to not form a new $2341$ pattern. This is relevant for us because of the following characterization of $2$-stack-sortable permutations due to West. 

\begin{theorem}[\cite{West}]\label{Thm8}
A permutation is $2$-stack-sortable if and only if it avoids the pattern $2341$ and also avoids any $3241$ pattern that is not part of a $35241$ pattern. 
\end{theorem}  

The recurrence in the next theorem provides the desired polynomial-time algorithm for computing $W_3(n)$. In what follows, let $B_{\geq\ell}^{(g)}(n)$ be the number of $3$-stack-sortable permutations $\sigma\in \mathcal W_3(n+\ell)$ such that $\tl(s(\sigma))\geq\ell$ and $\leg(s(\sigma))=\ell+g$. Let $C_n$ denote the $n^\text{th}$ Catalan number. 

\begin{theorem}[\cite{DefantCounting}]\label{Thm6}
If $n\geq 1$, then $W_3(n)=\sum_{g=1}^{n+1}B_{\geq 0}^{(g)}(n)$.
We have $B_{\geq\ell}^{(0)}(n)=0$ and \[B_{\geq\ell}^{(g)}(1)=\begin{cases} 0, & \mbox{if } g\neq 2; \\ C_{\ell+1}, & \mbox{if } g=2. \end{cases}\] If $n,g\geq 1$ and $\ell\geq 0$, then \[
B_{\geq\ell}^{(g)}(n+1)=\sum_{j=1}^\ell\left( \sum_{a=2}^{n}\sum_{b=\max\{2,g-a\}}^{g-1}\sum_{i=a-1}^{n-b+1} B_{\geq j-1}^{(a)}(i) B_{\geq \ell-j+1}^{(b)}(n-i)+ B_{\geq j-1}^{(g-1)}(n)C_{\ell-j+1}\right) \] \[+ B_{\geq\ell+1}^{(g-1)}(n).\] 
\end{theorem}

\begin{proof}
The first statement and the fact that $B_{\geq\ell}^{(0)}(n)=0$ are clear from the definitions we have given. The permutations $\sigma$ counted by $B_{\geq\ell}^{(g)}(1)$ are in $S_{\ell+1}$ and satisfy $\tl(s(\sigma))\geq\ell$, so they must actually satisfy $s(\sigma)=123\cdots(\ell+1)$. Since $\leg(123\cdots(\ell+1))=\ell+2$, the formula for $B_{\geq\ell}^{(g)}(1)$ follows from Theorem \ref{Thm1}. 

Now, let $B_\ell^{(g)}(n)$ be the number of $3$-stack-sortable permutations $\sigma\in \mathcal W_3(n+\ell)$ such that $\tl(s(\sigma))=\ell$ and $\leg(s(\sigma))=\ell+g$. Let 
\begin{equation}\label{Eq17}
\mathcal D_\ell^{(g)}(n)=\{\pi\in\mathcal W_2(n+\ell):\tl(\pi)=\ell,\,\leg(\pi)=\ell+g\}
\end{equation} and 
\begin{equation}\label{Eq18}
\mathcal D_{\geq\ell}^{(g)}(n)=\{\pi\in\mathcal W_2(n+\ell):\tl(\pi)\geq\ell,\,\leg(\pi)=\ell+g\}
\end{equation} so that \[B_\ell^{(g)}(n)=|s^{-1}(\mathcal D_\ell^{(g)}(n))|\quad\text{and}\quad B_{\geq\ell}^{(g)}(n)=|s^{-1}(\mathcal D_{\geq\ell}^{(g)}(n))|.\] We have $B_{\geq \ell}^{(g)}(n+1)=B_\ell^{(g)}(n+1)+B_{\geq\ell+1}^{(g-1)}(n)$, so we need to show that 
\begin{equation}\label{Eq16}
B_{\ell}^{(g)}(n+1)=\sum_{a=2}^{n}\sum_{b=\max\{2,g-a\}}^{g-1}\sum_{i=a-1}^{n-b+1}\sum_{j=1}^\ell B_{\geq j-1}^{(a)}(i) B_{\geq \ell-j+1}^{(b)}(n-i)+\sum_{j=1}^\ell B_{\geq j-1}^{(g-1)}(n)C_{\ell-j+1}. 
\end{equation}

Suppose $\pi\in\mathcal D_\ell^{(g)}(n+1)$ is such that $\pi_{n+1-i}=n+1$ (where $n\geq 0$). The Decomposition Lemma (Theorem~\ref{Cor1}) tells us that $|s^{-1}(\pi)|$ is equal to the number of triples $(H,\mu,\lambda)$, where $H\in\SW_{n+1-i}(\pi)$, $\mu\in s^{-1}(\pi_U^H)$, and $\lambda\in s^{-1}(\pi_S^H)$. Choosing $H$ amounts to choosing the number $j\in\{1,\ldots,\ell\}$ such that the northeast endpoint of $H$ is $(n+1+j,n+1+j)$. The permutation $\pi$ and the choice of $H$ determine the permutations $\pi_U^H$ and $\pi_S^H$. On the other hand, the choices of $H$ and the permutations $\pi_U^H$ and $\pi_S^H$ uniquely determine $\pi$. It follows that $B_\ell^{(g)}(n+1)$, which is the number of ways to choose an element of $s^{-1}(\mathcal D_\ell^{(g)}(n+1))$, is also the number of ways to choose $j$, the permutations $\pi_U^H$ and $\pi_S^H$, and the permutations $\mu$ and $\lambda$. Let us fix a choice of $j$. 

Assume for the moment that $i\leq n-1$, and let $r$ be the largest entry appearing to the left of $n+1$ in $\pi$. Because $\pi$ is $2$-stack-sortable, we can use Theorem \ref{Thm8} to see that $\pi_U^H$ is a permutation of the set $\{1,\ldots,n-i-1\}\cup\{r,n+1\}\cup\{n+2+j,\ldots,n+\ell+1\}$ and that $\pi_S^H$ is a permutation of $\{n-i,\ldots,n+j\}\setminus\{r,n+1\}$. Therefore, choosing $\pi_U^H$ and $\pi_S^H$ is equivalent to choosing their standardizations and the value of $r$. The standardization of $\pi_S^H$ is in $\mathcal D_{\geq j-1}^{(a)}(i)$ for some $a\in\{2,\ldots,i+1\}$, while the standardization of $\pi_U^H$ is in $\mathcal D_{\geq\ell-j+1}^{(b)}(n-i)$ for some $b\in\{2,\ldots,n-i+1\}$. Once we have chosen $a$ and $b$, the number of choices for $\pi_U^H,\mu,\pi_S^H,\lambda$ is $B_{\geq j-1}^{(a)}(i)B_{\geq \ell-j+1}^{(b)}(n-i)$.

Suppose we have already chosen the value of $a$. The fact that $\pi$ avoids $2341$ and the definition of a legal space tell us that there are $a$ possible values of $r$, say $\kappa_1<\cdots<\kappa_a$ (see Example \ref{Exam1} for an illustration of this part of the proof). If we choose $r=\kappa_m$, then $\pi$ has $a+b-m+1+\ell$ legal spaces. We are assuming that $\leg(\pi)=\ell+g$, so $g=a+b-m+1$. It follows that $2\leq a\leq n$ and $\max\{2,g-a\}\leq b\leq g-1$. Since $a\in\{2,\ldots,i+1\}$ and $b\in\{2,\ldots,n-i+1\}$, we also have the constraint $a-1\leq i\leq n-b+1$. This explains the expression $\sum_{a=2}^{n}\sum_{b=\max\{2,g-a\}}^{g-1}\sum_{i=a-1}^{n-b+1}\sum_{j=1}^\ell B_{\geq j-1}^{(a)}(i) B_{\geq \ell-j+1}^{(b)}(n-i)$ in \eqref{Eq16}. 

The expression $\sum_{j=1}^\ell B_{\geq j-1}^{(g-1)}(n)C_{\ell-j+1}$ in \eqref{Eq16} comes from the case in which $i=n$. In this case, $\pi_S^H$ is in $\mathcal D_{\geq j-1}^{(g-1)}(n)$, and $\pi_U^H=(n+1)(n+2+j)(n+3+j)\cdots(n+\ell+1)$ is an increasing permutation of size $\ell-j+1$. The number of choices for $\pi_S^H$ and $\lambda$ is $B_{\geq j-1}^{(g-1)}(n)$. The number of choices for $\mu$ is $|s^{-1}(\pi_U^H)|=C_{\ell-j+1}$. 
\end{proof}

\begin{example}\label{Exam1}
Consider the part of the proof of Theorem \ref{Thm6} in which we have already chosen $n,g,\ell,j,i$ and have assumed $i\leq n-1$. Suppose $n=8$, $\ell=5$, $j=2$, and $i=5$. If we choose the standardization of $\pi_U^H$ to be $24315678$ and choose the standardization of $\pi_S^H$ to be $315246$, then $a=\leg(315246)-(j-1)=5$ and $b=\leg(24315678)-(\ell-j+1)=4$. The green squares in Figure~\ref{Fig3} represent the possible choices for $r$, which are $\kappa_1=4$, $\kappa_2=5$, $\kappa_3=7$, $\kappa_4=8$, and $\kappa_5=9$. If $r=\kappa_m$, then we can refer to this figure to see that $\leg(\pi)=15-m=\ell+a+b-m+1$. Hence, the choice of $r$ is determined by $g$.  

\begin{figure}[h]
\begin{center}
\includegraphics[width=.4\linewidth]{3StackPIC2}
\caption{The decomposition of $\pi$ into $\pi_U^H$ and $\pi_S^H$ with the possible choices for $r$.}
\label{Fig3}
\end{center}  
\end{figure}
\end{example}

In \cite{DefantCounting}, the author used a generalization of the Decomposition Lemma to find a recurrence that counts $3$-stack-sortable permutations according to the statistics $\des$ and $\peak$. In \cite{DefantTroupes}, he obtained recurrences that enumerate $3$-stack-sortable alternating permutations of odd size and $3$-stack-sortable permutations in which all descents are peaks. 

\section{Data Analysis}

It is known that for each $t\geq 1$, the limit $\lim\limits_{n\to\infty}W_t(n)^{1/n}$ exists and is equal to $\sup\limits_{n\geq 1}W_t(n)^{1/n}$. Therefore, one can obtain lower bounds for this limit by computing values of $W_t(n)$. In \cite{DefantCounting}, the author computed $W_3(174)$ and concluded that $\lim\limits_{n\to\infty}W_3(n)^{1/n}\geq 8.6597$; this was the first nontrivial lower bound for this limit. B\'ona had conjectured that $W_3(n)\leq\binom{4n}{n}$ and that the sequence $(W_3(n))_{n\geq 1}$ is log-convex; the computations of $W_3(n)$ for $1\leq n\leq 174$ in \cite{DefantCounting} allowed the author to conclude that these two conjectures cannot both be true. 

More recently, Elvey Price, Guttmann, and the current author \cite{DefantElveyPrice} have modified the argument given in Section~\ref{Sec:3-Stack} in order to obtain a functional equation satisfied by the generating function that counts $3$-stack-sortable permutations; this was used to compute $W_3(n)$ for $1\leq n\leq 1000$. As a corollary, it was shown that $\lim\limits_{n\to\infty}W_3(n)^{1/n}\geq 9.4854$, which fully disproves B\'ona's conjecture that $W_3(n)\leq\binom{4n}{n}$. This new data was also used to give very precise conjectures about the asymptotic nature of the sequence $(W_3(n))_{n\geq 1}$; in particular, it was conjectured that $\lim\limits_{n\to\infty}W_3(n)^{1/n}\approx 9.69963634535$.  

Another outstanding conjecture in the field of stack-sorting, also due to B\'ona, states that for all $n,t\geq 1$, the polynomial $\sum_{\sigma\in\mathcal W_t(n)}x^{\des(\sigma)+1}$ has only real roots. So far, this conjecture is only known to be true when $t\leq 2$ or $t\geq n-2$. Using the previously-mentioned recurrence for counting $3$-stack-sortable permutations according to the statistics $\des$ and $\peak$ (specialized so as to ignore the peak statistic), the author found \cite{DefantCounting} that this real-rootedness conjecture holds when $t=3$ and $n\leq 43$. 

As explained more precisely in \cite{DefantCounting}, B\'ona has also conjectured that the numbers $W_3(n)$ are ``rarely odd.'' However, the values of $W_3(n)$ for $1\leq n\leq 174$ suggest that this conjecture is false.  


\section{Lower Bounds for $t$-Stack-Sortable Permutations}\label{Sec:Lower}

This final section gives the first nontrivial lower bound for $\lim\limits_{n\to\infty}W_t(n)^{1/n}$ when $t\geq 4$. 

\begin{theorem}[\cite{DefantCounting}]\label{Thm4}
For every $t\geq 1$, we have \[\lim_{n\to\infty}W_t(n)^{1/n}\geq(\sqrt t+1)^2.\]
\end{theorem}

\begin{proof}
Let $\Gamma_t$ be the set of all $\kappa=\kappa_1\cdots\kappa_{t+2}\in S_{t+2}$ such that $\kappa_{t+1}=t+2$ and $\kappa_{t+2}=1$. Let $\Av_n(\Gamma_t)$ be the set of permutations in $S_n$ that avoid all of the patterns in $\Gamma_t$. After applying a dihedral symmetry to the permutations in $\Gamma_t$, we can use Kremer's main result in \cite{Kremer} to see that 
\begin{equation}\label{Eq22}
\sum_{n\geq t}|\Av_n(\Gamma_t)|x^n=(t-1)!x^{t-2}\frac{1+(t-1)x-\sqrt{1-2(t+1)x+(t-1)^2x^2}}{2}.
\end{equation}
Some basic singularity analysis now shows that $\lim\limits_{n\to\infty}|\Av_n(\Gamma_t)|^{1/n}=(\sqrt{t}+1)^2$. 

We will prove by induction that $\Av_n(\Gamma_t)\subseteq\mathcal W_t(n)$. Since $\Gamma_1=\{231\}$, this is certainly true for $t=1$ (by Theorem \ref{Thm1}). Now suppose that $t\geq 2$ and that $\Av_n(\Gamma_{t-1})\subseteq\mathcal W_{t-1}(n)$. Choose a permutation $\pi\in S_n\setminus\mathcal W_t(n)$. This means that $s(\pi)\not\in\mathcal W_{t-1}(n)$, so $s(\pi)$ contains a permutation in $\Gamma_{t-1}$. In other words, there exist entries $b_1,\ldots,b_{t-1},c,a$ that appear in this order in $s(\pi)$ and satisfy $a<b_j<c$ for all $j\in\{1,\ldots,t-1\}$. Because $c$ appears to the left of $a$ in $s(\pi)$, it follows from the definition of $s$ that there must be an entry $d>c$ that appears to the right of $c$ and to the left of $a$ in $\pi$. The entries $b_1,\ldots,b_{t-1}$ must appear to the left of $d$ in $\pi$ since they would appear to the right of $c$ in $s(\pi)$ otherwise. The subpermutation of $\pi$ formed by the entries $a,b_1,\ldots,b_{t-1},c,d$ has a standardization that is in $\Gamma_t$, so $\pi\not\in\Av_n(\Gamma_t)$. This completes the induction. 
\end{proof}



Smith \cite{Smith} investigated a variant of the stack-sorting map known as the ``left-greedy algorithm.'' Let $\widehat{\mathcal W}_t(n)$ be the set of permutations in $S_n$ that can be sorted by $t$ stacks in series using the left-greedy algorithm (see \cite{Smith} for definitions). Smith proved that $\mathcal W_t(n)\subseteq\widehat{\mathcal W}_t(n)$ and $\lim\limits_{n\to\infty}|\widehat{\mathcal W}_t(n)|^{1/n}\geq t+1$. The next corollary improves this estimate. 

\begin{corollary}[\cite{DefantCounting}]\label{Cor2}
For every $t\geq 1$, we have $\lim\limits_{n\to\infty}|\widehat{\mathcal W}_t(n)|^{1/n}\geq (\sqrt t+1)^2$. 
\end{corollary}

\printbibliography

\end{document}
