论文标题
将根树的嵌入到根本的树上
Counting embeddings of rooted trees into families of rooted trees
论文作者
论文摘要
部分订购的部分订购集合$ t $的部分订购集合$ s $的嵌入数量是$ t $同构至$ s $的子访问的数量。如果两者都只有$ s $和$ t $，只有一个独特的最大元素，我们将良好的嵌入方式定义为$ s $和$ t $重叠的最大元素的嵌入。我们研究了所有二进制树的质量和所有嵌入$ n $元素的良好和所有嵌入的数量，考虑两种情况：飞机（时代的命令很重要）和非平面。此外，我们研究了所有种植型$ n $的种植飞机树中生根poset $ s $的嵌入数量。在所有情况下，我们都会得出良好和所有嵌入的渐近行为，我们证明，在所有情况下，我们提供确切常数的良好嵌入与所有阶层的比率是$θ（1/\ sqrt {n}）$的比例。此外，我们表明该比率在飞机二进制案例中与$ s $不持续，并且在非平面二进制案例和种植的平面案例中以$ s $的渐近不折叠。最后，我们对$ S $断开连接的情况发表评论。
The number of embeddings of a partially ordered set $S$ in a partially ordered set $T$ is the number of subposets of $T$ isomorphic to $S$. If both, $S$ and $T$, have only one unique maximal element, we define good embeddings as those in which the maximal elements of $S$ and $T$ overlap. We investigate the number of good and all embeddings of a rooted poset $S$ in the family of all binary trees on $n$ elements considering two cases: plane (when the order of descendants matters) and non-plane. Furthermore, we study the number of embeddings of a rooted poset $S$ in the family of all planted plane trees of size $n$. We derive the asymptotic behaviour of good and all embeddings in all cases and we prove that the ratio of good embeddings to all is of the order $Θ(1/\sqrt{n})$ in all cases, where we provide the exact constants. Furthermore, we show that this ratio is non-decreasing with $S$ in the plane binary case and asymptotically non-decreasing with $S$ in the non-plane binary case and in the planted plane case. Finally, we comment on the case when $S$ is disconnected.
