Pop-stack sorting and its image : Permutations with overlapping runs

• Pop-stack sorting is an important variation for sorting permutations via a stack. A single iteration of pop-stack sorting is the transformation T : S-n -> S-n 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 S-n under T. This work is 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.

Ämnesord

NATURVETENSKAP  -- Matematik (hsv//swe)

NATURAL SCIENCES  -- Mathematics (hsv//eng)

Publikations- och innehållstyp

ref (ämneskategori)

art (ämneskategori)