Journal of Combinatorics

Volume 11 (2020)

Number 3

Descents in $t$-sorted permutations

Pages: 511 – 526

DOI: https://dx.doi.org/10.4310/JOC.2020.v11.n3.a5

Author

Colin Defant (Princeton University, Princeton, New Jersey, U.S.A.)

Abstract

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

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