Descents in $t$-Sorted Permutations

Abstract

Let $s$ denote West's stack-sorting map. A permutation is called $t-\text{sorted}$ if it is of the form $s^t(\hat{I}¼)$ for some permutation $\hat{I}¼$. We prove that the maximum number of descents that a $t$-sorted permutation of length $n$ can have is $\lfloor \frac{n-t}{2}\rfloor$. When $n$ and $t$ have the same parity and $t\ge 2$, we give a simple characterization of those $t$-sorted permutations in $S_n$ that attain this maximum. In particular, the number of such permutations is $(n-t-1)!!$.

11 pages, 5 figures