A complete enumeration of Ballot permutations avoiding sets of small patterns
A complete enumeration of Ballot permutations avoiding sets of small patterns
复制标题
DOI：
10.54550/eca2023v3s1r6
复制
发表时间：
2022-01
影响因子：
--
通讯作者：
Nathan Sun
中科院分区：
文献类型：
--
作者：
Nathan Sun
其前缀包含的上升数至少与下降数相同的排列称为选票排列。 Lin、Wang和Zhao之前已经枚举了避免小模式的选票排列，并提出了避免一对长度为$3$的排列的枚举选票排列问题。我们完全枚举了避免长度为 $3$ 的两种模式的选票排列，并将这些回避类别与其各自的递归关系和公式联系起来，这导致避免 $132$ 和 $312$ 的选票排列与 Dyck 路径的左因子之间存在有趣的双射。此外，我们还得出了选票排列的 Wilf 分类，避免了长度为 $3$ 的两个模式的集合，然后我们将结果扩展到完全枚举避免了长度为 $3$ 的三个模式的选票排列。
Permutations whose prefixes contain at least as many ascents as descents are called ballot permutations. Lin, Wang, and Zhao have previously enumerated ballot permutations avoiding small patterns and have proposed the problem of enumerating ballot permutations avoiding a pair of permutations of length $3$. We completely enumerate ballot permutations avoiding two patterns of length $3$ and we relate these avoidance classes with their respective recurrence relations and formulas, which leads to an interesting bijection between ballot permutations avoiding $132$ and $312$ with left factors of Dyck paths. In addition, we also conclude the Wilf-classification of ballot permutations avoiding sets of two patterns of length $3$, and we then extend our results to completely enumerate ballot permutations avoiding three patterns of length $3$.