1Alpen-Adria-Universität Klagenfurt, Klagenfurt, Austria 2Université de Paris Nord, Paris, France 3University of Washington, Seattle, USA 4KTH Royal Institute of Technology in Stockholm, Sweden
Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 395-402
Citer cet article
Andrei Asinowski; Cyril Banderier; Sara Billey; Benjamin Hackl; Svante Linusson; Andrei Asinowski; Cyril Banderier; Sara Billey; Benjamin Hackl; Svante Linusson. Pop-stack sorting and its image: Permutations with overlapping runs. Acta mathematica Universitatis Comenianae, Tome 88 (2019) no. 3, pp. 395-402. http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a6/
@article{AMUC_2019_88_3_a6,
author = {Andrei Asinowski and Cyril Banderier and Sara Billey and Benjamin Hackl and Svante Linusson and Andrei Asinowski and Cyril Banderier and Sara Billey and Benjamin Hackl and Svante Linusson},
title = { Pop-stack sorting and its image: {Permutations} with overlapping runs},
journal = {Acta mathematica Universitatis Comenianae},
pages = {395--402},
year = {2019},
volume = {88},
number = {3},
url = {http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a6/}
}
TY - JOUR
AU - Andrei Asinowski
AU - Cyril Banderier
AU - Sara Billey
AU - Benjamin Hackl
AU - Svante Linusson
AU - Andrei Asinowski
AU - Cyril Banderier
AU - Sara Billey
AU - Benjamin Hackl
AU - Svante Linusson
TI - Pop-stack sorting and its image: Permutations with overlapping runs
JO - Acta mathematica Universitatis Comenianae
PY - 2019
SP - 395
EP - 402
VL - 88
IS - 3
UR - http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a6/
ID - AMUC_2019_88_3_a6
ER -
%0 Journal Article
%A Andrei Asinowski
%A Cyril Banderier
%A Sara Billey
%A Benjamin Hackl
%A Svante Linusson
%A Andrei Asinowski
%A Cyril Banderier
%A Sara Billey
%A Benjamin Hackl
%A Svante Linusson
%T Pop-stack sorting and its image: Permutations with overlapping runs
%J Acta mathematica Universitatis Comenianae
%D 2019
%P 395-402
%V 88
%N 3
%U http://geodesic.mathdoc.fr/item/AMUC_2019_88_3_a6/
%F AMUC_2019_88_3_a6
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.
