By Shalosh B. Ekhad and Doron Zeilberger
(Exclusively published in the Personal Journal of Shalosh B. Ekhad and Doron Zeilberger and arxiv.org )
Written: July 19, 2016
Dedicated to Neil Sloane and the many contributors to the OEIS. Keep up the Good Work!
According to Neil Sloane, as narrated in the Brief History of the OEIS, the very first sequence, the one that "started it all", is OEIS sequence A435 (The 7th sequence from the bottom of this historic page labeled "W_{n,1}, p. 44" and that starts as follows:
1,8,78,944,13800,234237432, ... .
Neil needed to know a formula for the expectation (or average) of the random variable "total height" (sum of the distances to the root of all vertices) defined on the "sample space" of all "labeled rooted trees" (that Arthur Cayley famously proved has cardinality n^{n-1}). more than 50 years later, we continue this quest, and discover (rigorously-proved) formulas for the variance, skewness, kurtosis, all the way to the 12th moment (and if you have computer-time to spare, you are welcome to continue, using our Maple package).
One of us (DZ) is pledging a $100 donation to the OEIS foundation for an EXPLICIT expression for the probability density function of the limiting scaled distribution, i.e. the p.d.f. of the limit, as n goes to infinity, of (X_{n}-μ_{n})/σ_{n} .
Abstract: In this tribute to Neil Sloane, we revisit the first sequence in the On-Line Encyclopedia of Integer Sequences, sequence A435 (1, 8, 78, 944, 13800, 237432, 4708144, 105822432, ...), that he encountered when he was a graduate student, and when normalized gives the average total height of rooted labeled trees. We state rigorously-computed explicit expressions for the first twelve moments of the random variable `total height' on rooted labeled trees, and pledge to donate to the OEIS 100 dollars in honor of the first to find an explicit expression for the probability density function of the limiting scaled probability distribution, as n goes to infinity.
Added Feb. 23, 2017: It turns out that the limiting distribution was already known, and goes back (at least) to David Aldous in 1981. See the messages by Valentin Féray and Svante Janson accompanying this follow up paper .
the input file generates the output file.
the input file generates the output file.
See pictures