Geodesic
Sorting with pattern-avoiding stacks: the \(132\)-machine
Giulio Cerbai1 ; Anders Claesson2 ; Luca Ferrari1 ; Einar Steingrímsson3
1University of Firenze
2Science Institute, University of Iceland, Iceland
3Department of Mathematics and Statistics, University of Strathclyde, Glasgow, Scotland
The electronic journal of combinatorics, Tome 27 (2020) no. 3
Cet article a éte moissonné depuis la source The Electronic Journal of Combinatorics website

Voir la notice de l'article

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.
DOI : 10.37236/9642
Classification : 05A05, 05A10, 05A15, 05A18, 05A19, 68P10
Mots-clés : pattern-avoiding sorting machines

Giulio Cerbai  1   ; Anders Claesson  2   ; Luca Ferrari  1   ; Einar Steingrímsson  3

1 University of Firenze
2 Science Institute, University of Iceland, Iceland
3 Department of Mathematics and Statistics, University of Strathclyde, Glasgow, Scotland 
@article{10_37236_9642,
     author = {Giulio Cerbai and Anders Claesson and Luca Ferrari and Einar Steingr{\'\i}msson},
     title = {Sorting with pattern-avoiding stacks: the \(132\)-machine},
     journal = {The electronic journal of combinatorics},
     year = {2020},
     volume = {27},
     number = {3},
     doi = {10.37236/9642},
     zbl = {1446.05003},
     url = {http://geodesic.mathdoc.fr/articles/10.37236/9642/}
}
TY  - JOUR
AU  - Giulio Cerbai
AU  - Anders Claesson
AU  - Luca Ferrari
AU  - Einar Steingrímsson
TI  - Sorting with pattern-avoiding stacks: the \(132\)-machine
JO  - The electronic journal of combinatorics
PY  - 2020
VL  - 27
IS  - 3
UR  - http://geodesic.mathdoc.fr/articles/10.37236/9642/
DO  - 10.37236/9642
ID  - 10_37236_9642
ER  - 
%0 Journal Article
%A Giulio Cerbai
%A Anders Claesson
%A Luca Ferrari
%A Einar Steingrímsson
%T Sorting with pattern-avoiding stacks: the \(132\)-machine
%J The electronic journal of combinatorics
%D 2020
%V 27
%N 3
%U http://geodesic.mathdoc.fr/articles/10.37236/9642/
%R 10.37236/9642
%F 10_37236_9642
Giulio Cerbai; Anders Claesson; Luca Ferrari; Einar Steingrímsson. Sorting with pattern-avoiding stacks: the \(132\)-machine. The electronic journal of combinatorics, Tome 27 (2020) no. 3. doi: 10.37236/9642

Cité par Sources :