An Asymptotic Ratio in the Complete Binary Tree |
| |
Authors: | Grzegorz Kubicki Jenő Lehel Michał Morayne |
| |
Affiliation: | (1) Department of Mathematics, University of Louisville, Louisville, KY, 40292, U.S.A.;(2) Institute of Mathematics, Wrocław University of Technology, Wybrzeże Wyspiańskiego 27, 50–370 Wrocław, Poland |
| |
Abstract: | 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. |
| |
Keywords: | tree poset embedding enumeration |
本文献已被 SpringerLink 等数据库收录! |
|