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
Doron Zeilberger's Home Page
Andrew Lohr's Home Page