Highly Sorted Permutations and Bell Numbers

Abstract

Let $s$ denote West's stack-sorting map. For all positive integers $m$ and all integers $n\ge 2m-2$, we give a simple characterization of the set $s^{n-m}(S_n)$; as a consequence, we find that $|s^{n-m}(S_n)|$ is the $m^{\text{th}}$ Bell number $B_m$. We also prove that the restriction $n\ge 2m-2$ is tight by showing that $|s^{m-3}(S_{2m-3})|=B_m+m-2$ for all $m\ge 3$.

8 pages, 1 figure