Generalized Stack Permutations
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)].
- A simplicial complex of 2-stack sortable permutations
- On the least exponential growth admitting uncountably many closed permutation classes
- Stack-sorting preimages of permutation classes
- scientific article; zbMATH DE number 1780162 (Why is no real title available?)
- A survey of stack sortable permutations
- Permutations of a multiset avoiding permutations of length 3
- Sorting with networks of data structures
- Sorting inversion sequences
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)