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 
.
Wen and Yan (2026) constructed a bijection between 2-stack-sortable permutations and permutations avoiding the classical permutation
pattern 3142 and the vincular pattern 
-
-
,
in which the entries corresponding to 4 and 1 must be adjacent. Their bijection preserves
jointly the number of direct-sum components, the number of ascents,
the length of the initial decreasing run, and the number of right-to-left maxima.
Here a direct-sum component is a block in the unique decomposition into permutations
that cannot be split into two consecutive blocks with every value of the first smaller
than every value of the second.
