论文标题
限制堆栈作为功能
Restricted Stacks as Functions
论文作者
论文摘要
多年来，堆栈排序算法一直是广泛研究的主题。在本文中，我们探讨了该算法的广义版本，其中堆栈避免了一组$ t $的排列。我们让$ s_t $表示这张地图。我们为哪些设置$ t $进行分类，地图$ s_t $是两种五个$。这种推论回答了Baril，Cerbai，Khalil和Vajnovszki的问题，内容涉及由$ s _ {\ {σ，τ\}} $组成的堆栈排序，称为$（σ，τ）$ - 机器。这完全分类为$σ$和$τ$在$（σ，τ）$ - 机器下的身份的预先形象由加泰罗尼亚数字计数。我们还证明，地图$ s_t $下的排列的预图数受加泰罗尼亚数字的界限，并随着索引的转换而限制。对于$ 1的尺寸1，我们在此界面较尖锐的时候进行了准确分类。我们还探讨了包含两个长度$ 3 $排列的各种$ s_t $的定期点和最大数量。
The stack sort algorithm has been the subject of extensive study over the years. In this paper we explore a generalized version of this algorithm where instead of avoiding a single decrease, the stack avoids a set $T$ of permutations. We let $s_T$ denote this map. We classify for which sets $T$ the map $s_T$ is bijective. A corollary to this answers a question of Baril, Cerbai, Khalil, and Vajnovszki about stack sort composed with $s_{\{σ,τ\}}$, known as the $(σ,τ)$-machine. This fully classifies for which $σ$ and $τ$ the preimage of the identity under the $(σ,τ)$-machine is counted by the Catalan numbers. We also prove that the number of preimages of a permutation under the map $s_T$ is bounded by the Catalan numbers, with a shift of indices. For $T$ of size 1, we classify exactly when this bound is sharp. We also explore the periodic points and maximum number of preimages of various $s_T$ for $T$ containing two length $3$ permutations.
