2019/07/18 by Cerbai, Giulio, Claesson, Anders, Ferrari, Luca
#Combinatorics (math.CO) #Data Structures and Algorithms (cs.DS) #Discrete Mathematics (cs.DM) #FOS: Computer and information sciences #FOS: Mathematics
paper · doi:10.48550/arxiv.1907.08142
The (classical) problem of characterizing and enumerating permutations that can be sorted using two stacks connected in series is still largely open. In the present paper we address a related problem, in which we impose restrictions both on the procedure and on the stacks. More precisely, we consider a greedy algorithm where we perform the rightmost legal operation (here "rightmost" refers to the usual representation of stack sorting problems). Moreover, the first stack is required to be σ-avoiding, for some permutation σ, meaning that, at each step, the elements maintained in the stack avoid the pattern σ when read from top to bottom. Since the set of permutations which can be sorted by such a device (which we call σ-machine) is not always a class, it would be interesting to understand when it happens. We will prove that the set of σ-machines whose associated sortable permutations are not a class is counted by Catalan numbers. Moreover, we will analyze two specific σ-machines in full details (namely when σ=321 and σ=123), providing for each of them a complete characterization and enumeration of sortable permutations.