Multi-static enumeration of two-stack sortable permutations
The permutations being counted are words of length \(n\) \((n\geq0)\) in the alphabet \(\{1,2,\dots,n\}\), no symbol being repeated. The mapping \(T\) is defined recursively: the empty word is mapped onto itself; if \(\sigma=\sigma^{(\ell)}n\sigma^{(r)}\) is such a word, then \(T(\sigma)=T(\sigma^{(\ell)}) T(\sigma^{(r)})n\). A permutation \(\sigma\) is \(k\)-stack-sortable if \(k\) successive applications of \(T\) yield \(123\dots n\). The numbers of 1-stack-sortable and 2-stack-sortable permutations have been determined by \textit{D. Knuth} [The art of computer programming, Volume 1, Fundamental algorithms, Addison-Wesley, Reading, Mass. (1958) p. 238] and \textit{D. Zeilberger} [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)!)\), Discrete Math. 102, No. 1, 85-93 (1992; Zbl 0754.05006)] respectively. ``In this paper we shall enumerate two-stack-sortable permutations \(\sigma=\sigma_1\sigma_2\dots\sigma_n\) according to the following classic statistics: the length \(n\); i.e. the number of \(i\in\{1,2,\dots,n\}\) such that \(\sigma(i)>\sigma(i+1)\) \dots; the number of right-to-left maxima, i.e. the number of \(i\in\{1,2,\dots,n\}\) such that \(\sigma(i)>\sigma(j)\) for all \(j>i\); the number of left-to-right maxima, i.e. the number of \(i\in\{1,2,\dots,n\}\) such that \(\sigma(i)>\sigma(j)\) for all \(j<i\). Moreover, using Zeilberger's factorization requires (us) to introduce another statistic \(\ell(\sigma)= \max\{\ell:\sigma^{-1}(n)<\sigma^{-1}(n-1)<\cdots< \sigma^{-1}(n-\ell+1)\}\dots\). We \(\dots\) prove that our five-variable generating function for two-stack-sortable permutations is algebraic of degree 20.
- Decompositions and statistics for \(\beta \)(1,0)-trees and nonseparable permutations
- 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)\)!)
- Description trees and Tutte formulas.
- A simplicial complex of 2-stack sortable permutations
- 132-avoiding two-stack sortable permutations, Fibonacci numbers, and Pell numbers
- Raney paths and a combinatorial relationship between rooted nonseparable planar maps and two-stack-sortable permutations
- Stack words, standard tableaux and Baxter permutations
- Further bijections to pattern-avoiding valid hook configurations
- Asymptotics of 3-stack-sortable permutations
- Stack-sorting with consecutive-pattern-avoiding stacks
- Troupes, cumulants, and stack-sorting
- Stack-sorting preimages of permutation classes
- Counting 3-stack-sortable permutations
- Permutations generated by a depth 2 stack and an infinite stack in series are algebraic
- Polynomial equations with one catalytic variable, algebraic series and map enumeration
- Fighting fish and two-stack sortable permutations
- New equivalences for pattern avoiding involutions
- Stack-sortable permutations and polynomials
- Refined enumeration of permutations sorted with two stacks and a D₈-symmetry
- Permutations sortable by two stacks in parallel and quarter plane walks
- Enumeration of Stack-Sorting Preimages via a Decomposition Lemma
- Lattice paths and pattern-avoiding uniquely sorted permutations
- Fertility, Strong Fertility, and Postorder Wilf Equivalence
- Asymptotic normality in t-stack sortable permutations
- On linear transformations preserving the Pólya frequency property
- Enumerating permutations sortable by k passes through a pop-stack
- Sorting with networks of data structures
- Counting Pop-Stacked Permutations in Polynomial Time
- Vincular pattern avoidance on cyclic permutations
- Non-overlapping descents and ascents in stack-sortable permutations
- Periodic points of consecutive-pattern-avoiding stack-sorting maps
- A direct bijection between two-stack sortable permutations and fighting fish (extended abstract)
- Stack words and a bound for 3-stack sortable permutations
This page was built for publication: Multi-static enumeration of two-stack sortable permutations
Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q1383515)
