Asymptotics of the Average Stack-Sorting Depth

Let ${\mathcal{D}}_n$ denote the average number of passes of the stack-sorting map $s$ required to sort a permutation in $S_n$. We use the recently introduced framework of stack-sorting diagrams and tableaux to prove that the limit ${\lim }_{n\to \mathrm{\infty }}{\mathcal{D}}_n\mathrm{/}n$ exists. This resolves a longstanding conjecture of West originally proposed in $1990$. As a consequence, we also provide a monotonically increasing sequence that converges to ${\lim }_{n\to \mathrm{\infty }}{\mathcal{D}}_n\mathrm{/}n$, improving upon Defant’s lower bound of $\lambda \approx 0.62433$.