Counting embeddings of rooted trees into families of rooted trees
share
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/√(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.
READ FULL TEXT