Stack sorting with restricted stacks

JOURNAL OF COMBINATORIAL THEORY SERIES A

卷:173

Article

Cerbai, Giulio¹  Claesson, Anders²  Ferrari, Luca¹ 

[1] Univ Firenze, Dipartimento Matemat & Informat U Dini, Florence, Italy

[2] Univ Iceland, Sci Inst, Reykjavik, Iceland

关键词: Permutation pattern;    Stacksort;    Catalan numbers;    Generating function;   

DOI  :  10.1016/j.jcta.2020.105230

来源: Elsevier

【 摘 要 】

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 sigma-avoiding, for some permutation sigma, meaning that the elements maintained in the stack avoid the pattern sigma when read from top to bottom. Since the set of permutations which can be sorted by such a device, which we call a sigma-machine, is not always a class, it would be interesting to understand when it happens. We prove that the set of sigma-machines whose associated sortable permutations are not a class is counted by Catalan numbers. Moreover, we analyze two specific sigma-machines in full detail (namely sigma = 321and sigma = 123), providing for each of them a complete characterization and enumeration of the sortable permutations. (c) 2020 Elsevier Inc. All rights reserved.

【 授权许可】

Free