论文标题
用避开图案的堆栈进行分类：$ 132 $ -MACHINE
Sorting with pattern-avoiding stacks: the $132$-machine
论文作者
论文摘要
本文继续对Cerbai，Claesson和Ferrari [CCF]最近引入的避免模式的分类机进行分析。这些设备由两个堆栈组成，通过将置换量通过，以便对其进行排序，每个堆栈的内容始终必须避免某种模式。在这里，我们表征并枚举当第一个堆栈为$ 132 $ - 避免$ 132 $的排列集，并解决[CCF]中提出的一个开放问题之一。为此，我们与其他众所周知的组合对象（例如晶格路径和受限生长功能（编码设置分区））提出了多个连接。我们还为列举某些避免模式的限制增长功能提供了新的证据，我们希望可以采用额有效地使用引入的工具来获得进一步的相似结果。
This paper continues the analysis of the pattern-avoiding sorting machines recently introduced by Cerbai, Claesson and Ferrari [CCF]. These devices consist of two stacks, through which a permutation is passed in order to sort it, where the content of each stack must at all times avoid a certain pattern. Here we characterize and enumerate the set of permutations that can be sorted when the first stack is $132$-avoiding, solving one of the open problems proposed in [CCF]. To that end we present several connections with other well known combinatorial objects, such as lattice paths and restricted growth functions (which encode set partitions). We also provide new proofs for the enumeration of some sets of pattern-avoiding restricted growth functions and we expect that the tools introduced can be fruitfully employed to get further similar results.
