Pop-stack sorting and its image: Permutations with overlapping runs
Main Article Content
Abstract
Pop-stack sorting is an important variation for sorting permutations via a stack. A single iteration of pop-stack sorting is the transformation T:Sn -> Sn that reverses all the maximal descending sequences of letters in a permutation. We investigate structural and enumerative aspects of pop-stacked permutations - the permutations that belong to the image of Sn under T. This work is a part of a project aiming to provide the full combinatorial analysis of sorting with a pop-stack, as it was successfully done for sorting with a stack (though, even in this case, some famous problems are still open). The first results already show that pop-stack sorting has a very rich combinatorial structure, and leads to surprising phenomena.
Article Details
How to Cite
Asinowski, A., Banderier, C., Billey, S., Hackl, B., & Linusson, S.
(2019).
Pop-stack sorting and its image: Permutations with overlapping runs.
Acta Mathematica Universitatis Comenianae, 88(3), 395-402.
Retrieved from http://www.iam.fmph.uniba.sk/amuc/ojs/index.php/amuc/article/view/1307/672
Issue
Section
EUROCOMB 2019