Contents Online

# 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

#### 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