An asymptotic ratio in the complete binary tree (Q1425163): Difference between revisions

Let \(T_n\) be the complete binary tree of height \(n\) considered as the Hasse-diagram of a poset with its root \(1\) as the maximum element. For a rooted tree \(T\) the number of embeddings of \(T\) into \(T_n\) is counted by functions \(A(n; T) = | \{S \subseteq T_n : 1 \in S, S \cong T\}| \) and \(B(n; T) = | \{S \subseteq T_n : 1 \notin S, S \cong T\}| \). In this sequel to ``A ratio inequality for binary trees and the best secretary'' [Comb. Probab. Comput. 11, No. 2, 149--161 (2002; Zbl 1005.60020)] by the same authors they show \[ \lim_{n\to\infty}[A(n;T) / B(n;T)] = 2^{\ell-1}-1 \] for every tree \(T\) with \(\ell\) leaves.