On The Limiting Distibutions of the Total Height On Families of Trees

By Andrew Lohr and Doron Zeilberger

.pdf   .ps   .tex
[Appeared in INTEGERS Volume 18 (2018), paper A32.]

First Written: Feb. 9, 2017; This version: March 3, 2017.

Here are

Abstract: A symbolic-computational algorithm, fully implemented in Maple, is described, that computes explicit expressions for generating functions that enable the efficient computations of the expectation, variance, and higher moments, of the random variable "sum of distances to the root", defined on any given family of rooted ordered trees (defined by degree restrictions).

Added Feb. 17, 2017: Read Valentin Féray's insightful email message commenting on the first version.

Added Feb. 21, 2017: Read Svante Janson's insightful email message commenting on the first version.
Added Feb. 23, 2017: It turns out (see the above two messages) that David Aldous has already proved our conjectured `universality' way back in 1981, and Svante Janson studied it extensively. A donation of \$100 to the OEIS Foundation, in honor of Valentin Féray and Svante Janson has been made.

Added March 6, 2016: These comments have been incorpoated into the second version.

Maple packages

• TREES.txt, a Maple package to study the statistical distribution of the random variable "total height" defined on ordered trees

• THS.txt, a Maple package to check the above package, by computing the quantities from first-principle.

Sample Input and Output for TREES.txt

• If you want to see an article about the average, variance, third and fourth moments, of the random variable `total height' defined on ordered trees where each vertex has 0,1, or 2 children

the input file generates the output file.

• If you want to see an article about the average, variance, third and fourth moments, of the random variable `total height' defined on ordered trees where each vertex has 0,1,2, or 3 children

the input file generates the output file.

• If you want to see an article about ordered COMPLETE Binary trees (with EXACT expressions for the first nine moments, as well as asymptotic ones`):

the input file generates the output file.

• If you want to see an article about the average, variance, third and fourth moments, of the random variable `total height' defined on ordered trees where each vertex has 0,2, or 3 children

the input file generates the output file.

• If you want to see an article about GENERATING FUNCTIONS that enables one to compute the average, variance, third and fourth moments, of the random variable `total height' defined on ordered trees where each vertex has 0,1,2,3, or 4 children

the input file generates the output file.

• If you want to see an article about GENERATING FUNCTIONS that enables one to compute the average and variance of the random variable `total height' defined on ordered trees where each vertex has 0, 2, or 5 vertices

the input file generates the output file.

• If you want to see an article about GENERATING FUNCTIONS that enables one to compute the average and variance of the random variable `total height' defined on ordered trees where each vertex has 0,1, 3, or 4 children

the input file generates the output file.

Sample Input and Output for THS.txt

• If you want to see the list of the first weight-enumerators, from n=1 to n=12, of the set of trees with n vertices where every vertex is either a leaf or has one or two children, computed from First-Principle

the input file generates the output file.

• If you want to see the list of the first weight-enumerators, from n=1 to n=12, of the set of trees with n vertices where every vertex is either a leaf or has one, two, or three children, computed from First-Principle

the input file generates the output file.

• If you want to see the list of the first weight-enumerators, from n=1 to n=12, of the set of trees with n vertices where every vertex is either a leaf or has three, four, or five children, computed from First-Principle

the input file generates the output file.

Articles of Doron Zeilberger