





















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.
此内容由惯性聚合(RSS阅读器)自动聚合整理,仅供阅读参考。 原文来自 — 版权归原作者所有。