An Asymptotic Ratio in the Complete Binary Tree

Let T _n be the complete binary tree of height n considered as the Hasse-diagram of a poset with its root 1 _n as the maximum element. For a rooted tree T, define two functions counting the embeddings of T into T _n as follows A(n;T)=|{S T _n  : 1 _n ∈S, S≅T}|, and B(n;T)=|{S T _n :1 _n ∉S, S≅T}|. In this paper we investigate the asymptotic behavior of the ratio A(n;T)/B(n;T), and we show that lim  _n→∞A(n;T)/B(n;T)]=2^ℓ;−1−1, for any tree T with ℓ leaves. This revised version was published online in June 2006 with corrections to the Cover Date.