Enumeration of General t-ary Trees and Universal Types

Zhilong ZHANG, Charles Knessl

Abstract


We consider t-ary trees characterized by their numbers of nodes and their total path length. When t=2 these are called binary trees, and in such trees a parent node may have up to t child nodes. We give asymptotic expansions for the total number of trees with nodes and path length p, when n and p are large. We consider several different ranges of n and p. For n→∞ and p=O(n^{3/2}) we recover the Airy distribution for the path length in trees with many nodes, and also obtain higher order asymptotic results. For p→∞ and an appropriate range of n we obtain a limiting Gaussian distribution for the number of nodes in trees with large path lengths. The mean and variance are expressed in terms of the maximal root of the Airy function. Singular perturbation methods, such as asymptotic matching and WKB type expansions, are used throughout, and they are combined with more standard methods of analytic combinatorics, such as generating functions, singularity analysis, saddle point method, etc. The results are applicable to problems in information theory, that involve data compression schemes which parse long sequence into shorter phrases. Numerical studies show the accuracy of the various asymptotic approximations. Key Words: Trees; Universal Types; Asymptotics; Path Length; Singular Perturbations

Full Text:

PDF


DOI: http://dx.doi.org/10.3968%2Fj.pam.1925252820120101.001

Refbacks

  • There are currently no refbacks.


Reminder

If you have already registered in Journal A and plan to submit article(s) to Journal B, please click the CATEGORIES, or JOURNALS A-Z on the right side of the "HOME".


We only use the follwoing mailboxes to deal with issues about paper acceptance, payment and submission of electronic versions of our journals to databases:
pam@cscanada.org
pam@cscanada.net

Copyright © 2010 Canadian Research & Development Center of Sciences and Cultures
Address: 758, 77e AV, Laval, Quebec, Canada H7V 4A8

Telephone: 1-514-558 6138
Http://www.cscanada.net
Http://www.cscanada.org
E-mail:office@cscanada.net office@cscanada.org caooc@hotmail.com