Generalized Stack Permutations

From MaRDI portal





The paper generalizes the concept of stack-sortable permutation to \((r,s)\)-stack-sortable permutation. A permutation is \((r,s)\)-stack-sortable, if it can be sorted by a sequence of extended push and pop operations. The extended push operation can insert a new element in any of the first \(r\) positions of the current permutation, while the extended pop operation can remove any of the first \(s\) elements. It turns out that \((r,s)\)-stack-sortable permutations correspond bijectively to \((s,r)\)-stack-sortable permutations. Counting \((r,s)\)-stack-sortable permutations is closely connected to counting permutations that avoid certain permutations. Knuth's classical result is that \((1,1)\)-stack-sortable permutations are those avoiding the permutation [2, 3, 1]. The paper proves that \((r,1)\)-stack-sortable permutations are exactly those that avoid all \(r!\) permutations of the form \([a_1,a_2, \dots, a_r,\;r+2,1]\). An asymptotic formula is given for the number of them. The paper proves that \((2, 2)\)-stack-sortable permutations are exactly those that avoid certain 8 permutations. For recent important results on permutation avoidance not cited in the paper, see \textit{M. Bóna} [Discrete Math. 181, No. 1-3, 267-274 (1998; Zbl 0896.05004)], [J. Comb. Theory, Ser. A 80, No. 2, 257-272, Art. No. TA972800 (1997; Zbl 0887.05004)], and [Discrete Math. 175, No. 1-3, 55-67 (1997; Zbl 0888.05002)].











This page was built for publication: Generalized Stack Permutations

Report a bug (only for logged in users!)Click here to report a bug for this page (MaRDI item Q4228200)