Stack-sortable permutations and beyond
\textit{D. E. Knuth} [The art of computer programming. Vol. 1: Fundamental algorithms. 3rd ed. Reading, MA: Addison-Wesley (1997; Zbl 0895.68055)] classified and counted permutations which can be sorted using a stack data structure. This was later generalized to permutations sorted by two iterations of the stack, also known as 2-stack-sortable. \textit{J. West} [Permutations with restricted subsequences and stack-sortable permutations. MIT (PhD thesis) (1990)] conjectured a formula for the number of 2-stack-sortable permutations and \textit{D. Zeilberger} [Discrete Math. 102, No. 1, 85--93 (1992; Zbl 0754.05006)] proved this formula. In this expository article, the author surveys the state-of-the-art in the theory of \(t\)-stack-sortable permutations for \(t \geq 2\). The key result is a decomposition lemma due to the author, which he successfully uses to establish asymptotic bounds on the number of 3-stack-sortable permutations, thereby disproving a conjecture of Bóna (see [\textit{C. Defant}, J. Comb. Theory, Ser. A 172, Article ID 105209, 26 p. (2020; Zbl 1433.05005)]). He also gives a new proof of the number of 2-stack-sortable permutations and gives nontrivial lower bounds for the number of \(t\)-stack-sortable permutations when \(t \geq 4\).
- A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
- Asymptotics of 3-stack-sortable permutations
- Comparing algorithms for sorting with t stacks in series
- Counting 3-stack-sortable permutations
- Describing West-3-stack-sortable permutations with permutation patterns
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Fertility monotonicity and average complexity of the stack-sorting map
- scientific article; zbMATH DE number 3303654 (Why is no real title available?)
- Permutations with forbidden subsequences and a generalized Schröder number
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- Preimages under the stack-sorting algorithm
- Troupes, cumulants, and stack-sorting
- A proof of Julian West's conjecture that the number of two-stack-sortable permutations of length \(n\) is \(2(3n)\)!/(\((n+1)\)!\((2n+1)\)!)
- Multi-static enumeration of two-stack sortable permutations
- A survey of stack-sorting disciplines
- A simplicial complex of 2-stack sortable permutations
- Restricted stacks as functions
- Asymptotics of 3-stack-sortable permutations
- Troupes, cumulants, and stack-sorting
- Stack-sorting preimages of permutation classes
- Fertility monotonicity and average complexity of the stack-sorting map
- Stack sorting with increasing and decreasing stacks
- Counting 3-stack-sortable permutations
- Preimages under the stack-sorting algorithm
- 2-stack sorting is polynomial
- Fighting fish and two-stack sortable permutations
- Lattice paths and \((n - 2)\)-stack sortable permutations
- Efficient methods of calculating the number of heapable permutations
- Stacking Blocks and Counting Permutations
- Stack-sorting for words
- Stack-sortable permutations and polynomials
- Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
- Revstack sort, zigzag patterns, descent polynomials of t-revstack sortable permutations, and Steingrímsson's sorting conjecture
- Generalized Stack Permutations
- scientific article; zbMATH DE number 1780162 (Why is no real title available?)
- Permutations sortable by two stacks in parallel and quarter plane walks
- Passing through a stack k times
- Toppleable permutations, excedances and acyclic orientations
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Highly sorted permutations and Bell numbers
- A survey of stack sortable permutations
- Asymptotic normality in t-stack sortable permutations
- Sorting and preimages of pattern classes
- Enumerating permutations sortable by k passes through a pop-stack
- Counting Pop-Stacked Permutations in Polynomial Time
- Highly sorted permutations with respect to a 312-avoiding stack
- Troupes, cumulants, and stack-sorting
- Non-overlapping descents and ascents in stack-sortable permutations
- The order of the (123, 132)-avoiding stack sort
- On a conjecture on pattern-avoiding machines
- Describing West-3-stack-sortable permutations with permutation patterns
- Stack words and a bound for 3-stack sortable permutations
This page was built for publication: Stack-sortable permutations and beyond
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q2680951)
