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

Abstract

We study the behavior of West's stack-sorting map $s$ on permutations whose last entry is also their least. Let $S_n^{\prime }:=\{\pi 0\mid \ddot{I}€\in S_n\}$ where $\pi 0$ denotes the concatenation of $\ddot{I}€$ and $0$. For each permutation $\ddot{I}€\in S_n^{\prime }$, we introduce a new combinatorial object known as the stack-sorting tableau $T_{\ddot{I}}€$, 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^{\prime }$. We then establish a precise relationship between the behavior of $s$ on $S_n^{\prime }$ and on $S_n$.

15 pages, 1 figure