Descents in $t$-sorted permutations

Let $s$ denote West’s stack-sorting map. A permutation is called $t$‑sorted if it is of the form $s^t (\mu)$ for some permutation $\mu$. 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 \geq 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)!!$.

Keywords

permutation, descent, stack-sorting, valid hook configuration

Full Text (PDF format)

The author was supported by a Fannie and John Hertz Foundation Fellowship and an NSF Graduate Research Fellowship.

Received 15 April 2019

Published 11 May 2020