论文标题
在根林中避免经典和连续的模式
Classical and consecutive pattern avoidance in rooted forests
论文作者
论文摘要
跟随安德斯（Anders）和弓箭手（Archer），我们说，一个无序的植根标记森林避免了\ Mathcal {s} _K $的模式$σ\如果在每棵树中，则沿着根部到顶点的最短路径沿每个标签序列都不包含与$σ$相同的相对顺序。对于每个排列$σ\ in \ nathcal {s} _ {k-2} $，我们在$ n $ -vertex森林之间构建了两次两次射击$（σ）k（k-1）：=σ（1）\cdotsσ（k-2）k（k-1）$，给出了西部对置换和安德斯的结果的共同概括 - 在森林上。我们进一步定义了一个新物体，即森林年代图，我们用来将其扩展到与森林相当的形状范围的概念。特别是，这使我们能够将上述结果概括为避免$ \ {（σ_1）k（k-1），（σ_2）k（k-1），\ dots，（σ_\ ell）k（k-el）k（k-1）$ and forests避免$ \ \ \ \ \ {（K-1）（K-1）K，（K-1）（k-1），（k-1）（k-1），（k-1）（k-1）（k-1）（k-1）（k-1）（k-1）（k-1）（k-1）， （σ_\ ell）（k-1）k \} $ for $σ_1，\ dots，σ_\ ell \ in \ Mathcal {s} _ {k-2} $。此外，我们给出列举的复发，以避免$ \ {123 \ cdots k \} $，$ \ {213 \} $和其他一组模式。最后，我们将Goulden-Jackson聚类方法扩展到研究安德斯和弓箭手定义的根树中的连续模式。使用广义群集方法，我们证明，如果两个长度 - $ k $模式是强c-福雷斯特 - wilf等效物，则进行互补，则两种模式必须以相同的数字开始。我们还证明了令人惊讶的结果，即$ 1324 $和$ 1423 $的模式相当于c-forest-wilf等效物，即使它们与排列相当于c-wilf。
Following Anders and Archer, we say that an unordered rooted labeled forest avoids the pattern $σ\in\mathcal{S}_k$ if in each tree, each sequence of labels along the shortest path from the root to a vertex does not contain a subsequence with the same relative order as $σ$. For each permutation $σ\in\mathcal{S}_{k-2}$, we construct a bijection between $n$-vertex forests avoiding $(σ)(k-1)k:=σ(1)\cdotsσ(k-2)(k-1)k$ and $n$-vertex forests avoiding $(σ)k(k-1):=σ(1)\cdotsσ(k-2)k(k-1)$, giving a common generalization of results of West on permutations and Anders--Archer on forests. We further define a new object, the forest-Young diagram, which we use to extend the notion of shape-Wilf equivalence to forests. In particular, this allows us to generalize the above result to a bijection between forests avoiding $\{(σ_1)k(k-1), (σ_2)k(k-1), \dots, (σ_\ell)k(k-1)\}$ and forests avoiding $\{(σ_1)(k-1)k, (σ_2)(k-1)k, \dots, (σ_\ell)(k-1)k\}$ for $σ_1, \dots, σ_\ell \in \mathcal{S}_{k-2}$. Furthermore, we give recurrences enumerating the forests avoiding $\{123\cdots k\}$, $\{213\}$, and other sets of patterns. Finally, we extend the Goulden--Jackson cluster method to study consecutive pattern avoidance in rooted trees as defined by Anders and Archer. Using the generalized cluster method, we prove that if two length-$k$ patterns are strong-c-forest-Wilf equivalent, then up to complementation, the two patterns must start with the same number. We also prove the surprising result that the patterns $1324$ and $1423$ are strong-c-forest-Wilf equivalent, even though they are not c-Wilf equivalent with respect to permutations.
