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.

For a positive integer and West's stack-sorting map , define the descent polynomial of a fiber by

where is the number of permutation descents of . Defant (2026) proved that its coefficient sequence is an ultra log-concave sequence of order . This does not assert that is real-rooted. Defant (2026) credits AxiomProver with finding the matroid used in the proof and formalizing the results.

See also

Catalan Number, Motzkin Number, Permutation, Permutation Pattern

Explore with Wolfram|Alpha

References

Bousquet-Mélou, M. "Sorted and/or Sortable Permutations." Disc. Math. 225, 25-50, 2000. https://doi.org/10.1016/S0012-365X(00)00146-1.Defant, C. "Log-Concavity in Narayana Transforms and Stack-Sorting Fibers." 10 Nov 2026. https://arxiv.org/abs/2611.13479v1.Inagaki, R. and Luo, M. "Motzkin Numbers Count 2-Stack-Sortable Permutations Ending in Their Least Entry." 2 Oct 2026. https://arxiv.org/abs/2610.02756.Wen, Y. and Yan, S. H. F. "On a Conjecture Concerning Two-Stack Sortable Permutations." 21 Oct 2026. https://arxiv.org/abs/2610.29115.

Cite this as:

Weisstein, Eric W. "Stack-Sortable Permutation." From MathWorld--A Wolfram Resource. https://mathworld.wolfram.com/Stack-SortablePermutation.html

Subject classifications