Lopsided trees, I: Analyses

Lopsided trees are rooted, ordered trees in which the length of an edge fro m a node to its ith child depends upon the value of i. These trees model a variety of problems and have therefore been extensively studied. In this pa per we combine analytic and combinatorial techniques to address three open problems on such trees: 1. Given n, characterize the combinatorial structure of a lopsided tree wit h n leaves that has minimal external path length. 2. Express the cost of the minimal external path length tree as a function of n. 3. Calculate exactly how many nodes of depth less than or equal to x exist in the infinite lopsided tree. Lopsided trees model Varn codes, prefix free codes in which the letters of the encoding alphabet can have different lengths. The solutions to the firs t and second problems above solve corresponding open problems on Varn codes . The solution to the third problem can be used to model the performance of broadcasting algorithms in the postal model of communication. Finding thes e solutions requires generalizing the definition of Fibonacci numbers and t hen using Mellin-transform techniques.