论文标题
一种基于生成树木用于枚举模式反演序列的树的算法方法
An algorithmic approach based on generating trees for enumerating pattern-avoiding inversion sequences
论文作者
论文摘要
我们引入了一种基于生成树方法的算法方法，用于列举具有各种模式避免限制的反转序列。对于给定的一组模式，我们提出了一种算法，该算法要么对相应生成树或Ansatz的继任规则进行准确描述。通过使用这种方法，我们确定图案级$ i_n（000，021），I_N（100，021）$，$ I_N（110，021），I_N（102，021）$，$ I_N（100,012）$，$ I_N（100,012）$，$ I_N（011,211,201）$，$ I__n（$ i_n（011,211）， $ i_n（120,210）$。然后，我们使用内核方法，获得每个类的生成功能，并找到枚举公式。 Lin和Yan研究了WILF等效度的分类，以避免成对的三个图案，并表明78对中有48个WILF类。在本文中，我们解决了此类模式类别的六个开放式案例。
We introduce an algorithmic approach based on generating tree method for enumerating the inversion sequences with various pattern-avoidance restrictions. For a given set of patterns, we propose an algorithm that outputs either an accurate description of the succession rules of the corresponding generating tree or an ansatz. By using this approach, we determine the generating trees for the pattern-classes $I_n(000, 021), I_n(100, 021)$, $I_n(110, 021), I_n(102, 021)$, $I_n(100,012)$, $I_n(011,201)$, $I_n(011,210)$ and $I_n(120,210)$. Then we use the kernel method, obtain generating functions of each class, and find enumerating formulas. Lin and Yan studied the classification of the Wilf-equivalences for inversion sequences avoiding pairs of length-three patterns and showed that there are 48 Wilf classes among 78 pairs. In this paper, we solve six open cases for such pattern classes.
