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. Moreover, the first stack is required to be σ-avoiding, for some permutation σ, meaning that 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 a σ-machine, is not always a class, it would be interesting to understand when it happens. We prove that the set of σ-machines whose associated sortable permutations are not a class is counted by Catalan numbers. Moreover, we analyze two specific σ-machines in full detail (namely σ=321 and σ=123), providing for each of them a complete characterization and enumeration of the sortable permutations.
Stack sorting with restricted stacks / Cerbai G.; Claesson A.; Ferrari L.. - In: JOURNAL OF COMBINATORIAL THEORY. SERIES A. - ISSN 0097-3165. - STAMPA. - 173, Article 105230:(2020), pp. 1-19. [10.1016/j.jcta.2020.105230]
Stack sorting with restricted stacks
Cerbai G.;Claesson A.;Ferrari L.
2020
Abstract
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. Moreover, the first stack is required to be σ-avoiding, for some permutation σ, meaning that 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 a σ-machine, is not always a class, it would be interesting to understand when it happens. We prove that the set of σ-machines whose associated sortable permutations are not a class is counted by Catalan numbers. Moreover, we analyze two specific σ-machines in full detail (namely σ=321 and σ=123), providing for each of them a complete characterization and enumeration of the sortable permutations.File | Dimensione | Formato | |
---|---|---|---|
nonclasses_revised.pdf
accesso aperto
Descrizione: Articolo principale
Tipologia:
Versione finale referata (Postprint, Accepted manuscript)
Licenza:
Creative commons
Dimensione
318.46 kB
Formato
Adobe PDF
|
318.46 kB | Adobe PDF |
I documenti in FLORE sono protetti da copyright e tutti i diritti sono riservati, salvo diversa indicazione.