Polynomial Time Enumeration of t-Stack-Sortable Permutations Ending in Their Least Entry

We study the behavior of West’s stack-sorting map $s$ on permutations whose last entry is also their least. Let $S_n^{\mathrm{\prime }}:=\{\pi 0\mid \pi \in S_n\}$ where $\pi 0$ denotes the concatenation of $\pi$ and $0$. For each permutation $\pi \in S_n^{\mathrm{\prime }}$, we introduce a new combinatorial object known as the stack-sorting tableau $T_{\pi }$, which ultimately serves as the key ingredient in the first polynomial time algorithm for counting the number of $t$-stack-sortable permutations in $S_n^{\mathrm{\prime }}$. We then establish a precise relationship between the behavior of $s$ on $S_n^{\mathrm{\prime }}$ and on $S_n$.