Motzkin Numbers Count 2-Stack-Sortable Permutations Ending in Their Least Entry

Ryota Inagaki, Michael Luo

We prove the following conjecture of Zhang (arXiv:2604.10779, Conjecture 6.1): for $n\ge 0$, the number of $2$-stack-sortable permutations of $\{0,1,\dots ,n\}$ ending in $0$ is t…