2025/03/11 by Cioni, Lapo, Ferrari, Luca, Smith, Rebecca
#05A05 #05A10 #05A15 #Combinatorics (math.CO) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics #G.2.1
paper · doi:10.48550/arxiv.2503.08285
We introduce a new sorting device for permutations which makes use of a pop stack augmented with a bypass operation. This results in a sorting machine, which is more powerful than the usual Popstacksort algorithm and seems to have never been investigated previously. In the present paper, we give a characterization of sortable permutations in terms of forbidden patterns and reinterpret the resulting enumerating sequence using a class of restricted Motzkin paths. Moreover, we describe an algorithm to compute the set of all preimages of a given permutation, thanks to which we characterize permutations having a small number of preimages. Finally, we provide a full description of the preimages of principal classes of permutations, and we discuss the device consisting of two pop stacks in parallel, again with a bypass operation.