论文标题
$σ$ -Machines的动态方面
Dynamical aspects of $σ$-machines
论文作者
论文摘要
Cerbai，Claesson和Ferrari最近引入了$σ$ -Machine，作为一种工具，可以更好地了解与两个串联串联分类排列问题的问题。它由两个连续的堆栈组成，这些堆栈在任何时候必须避免某种模式的意义上受到限制：在第一个堆栈中给定的$σ$，第二个堆栈中的$ 21 $。在这里，我们证明，在大多数情况下，可分配排列避免了双记模式$ξ$。我们提供了$ξ$避免排列的几何分解，并使用它直接计数它们。然后，我们表征了属性的排列，即$σ$ - 避免$σ$的输出不包含$σ$，我们称之为有效。对于$σ= 123 $，我们获得了一种列举可排序排列的替代方法。最后，我们对$σ$ -Machines进行了分类，并确定要研究的最具挑战性。
The $σ$-machine was recently introduced by Cerbai, Claesson and Ferrari as a tool to gain a better insight on the problem of sorting permutations with two stacks in series. It consists of two consecutive stacks, which are restricted in the sense that their content must at all times avoid a certain pattern: a given $σ$, in the first stack, and $21$, in the second. Here we prove that in most cases sortable permutations avoid a bivincular pattern $ξ$. We provide a geometric decomposition of $ξ$-avoiding permutations and use it to count them directly. Then we characterize the permutations with the property that the output of the $σ$-avoiding stack does not contain $σ$, which we call effective. For $σ=123$, we obtain an alternative method to enumerate sortable permutations. Finally, we classify $σ$-machines and determine the most challenging to be studied.
