Multi-static enumeration of two-stack sortable permutations (Q1383515)

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''.