A stack-sortable permutation is a permutation sorted into increasing order by a single application of the deterministic stack-sorting
map 
.
This map reads entries from left to right, pushes the next entry onto a stack if
the stack is empty or that entry is smaller than the top entry, and otherwise pops
the top entry into the output. After the input is exhausted, it pops the remaining
entries. More generally, a 
-stack-sortable permutation is sorted by at most 
applications of 
. For example, 
and 
, so 3142 is 2-stack-sortable.
The stack-sortable permutations are exactly those avoiding the permutation pattern 231, and
their number in the symmetric group 
is the Catalan number 
.
The number of 2-stack-sortable permutations in the
symmetric group 
is
 |
Inagaki and Luo (2026) proved that the number of 2-stack-sortable permutations of 
ending in 0 is the Motzkin number 
for every 
.
