TY - JOUR
T1 - Sorting with pattern-avoiding stacks
T2 - the 132-machine
AU - Cerbai, Giulio
AU - Claesson, Anders
AU - Ferrari, Luca
AU - Steingrímsson, Einar
PY - 2020/8/21
Y1 - 2020/8/21
N2 - This paper continues the analysis of the pattern-avoiding sorting machines recently introduced by Cerbai, Claesson and Ferrari (2020). These devices consist of two stacks, through which a permutation is passed in order to sort it, where the content of each stack must at all times avoid a certain pattern. Here we characterize and enumerate the set of permutations that can be sorted when the first stack is 132-avoiding, solving one of the open problems proposed by the above mentioned authors. To that end we present several connections with other well known combinatorial objects, such as lattice paths and restricted growth functions (which encode set partitions). We also provide new proofs for the enumeration of some sets of pattern-avoiding restricted growth functions and we expect that the tools introduced can be fruitfully employed to get further similar results.
AB - This paper continues the analysis of the pattern-avoiding sorting machines recently introduced by Cerbai, Claesson and Ferrari (2020). These devices consist of two stacks, through which a permutation is passed in order to sort it, where the content of each stack must at all times avoid a certain pattern. Here we characterize and enumerate the set of permutations that can be sorted when the first stack is 132-avoiding, solving one of the open problems proposed by the above mentioned authors. To that end we present several connections with other well known combinatorial objects, such as lattice paths and restricted growth functions (which encode set partitions). We also provide new proofs for the enumeration of some sets of pattern-avoiding restricted growth functions and we expect that the tools introduced can be fruitfully employed to get further similar results.
KW - pattern-avoiding sorting machine
KW - combinatorial objects
KW - stacksort
UR - http://www.scopus.com/inward/record.url?scp=85090530955&partnerID=8YFLogxK
U2 - 10.37236/9642
DO - 10.37236/9642
M3 - Article
AN - SCOPUS:85090530955
SN - 1077-8926
VL - 27
JO - Electronic Journal of Combinatorics
JF - Electronic Journal of Combinatorics
IS - 3
M1 - 3.32
ER -