Sorting Cayley permutations with pattern-avoiding machines
Sorting Cayley permutations with pattern-avoiding machines
复制标题
使用模式避免机对凯莱排列进行排序
DOI：
--
复制
发表时间：
2020
期刊：
影响因子：
--
通讯作者：
Giulio Cerbai
中科院分区：
文献类型：
--
作者：
Giulio Cerbai
模式避免机器是由Claesson、Ferrari和目前的作者为了更好地理解经典的$2$堆栈排序问题而引入的。在本文中，我们通过允许具有重复元素的排列来推广这些装置，也称为Cayley排列。主要结果是对这些模式的描述，使得对应的可排序排列集是一个类。我们还证明了Cayley置换集上的一个新的对合，这是通过将避免模式的堆栈视为一个算子而得到的。最后，我们分析了基于Cayley置换的POP堆栈排序的两个推广。在这两种情况下，我们都从模式避免的角度描述了可排序的排列。
Pattern avoiding machines were recently introduced by Claesson, Ferrari and the current author to gain a better understanding of the classical $2$-stacksort problem. In this paper we generalize these devices by allowing permutations with repeated elements, also known as Cayley permutations. The main result is a description of those patterns such that the corresponding set of sortable permutations is a class. We also show a new involution on the set of Cayley permutations, obtained by regarding a pattern-avoiding stack as an operator. Finally, we analyze two generalizations of pop-stack sorting on Cayley permutations. In both cases we describe sortable permutations in terms of pattern avoidance.