Going Back to Neil Sloane's FIRST LOVE (OEIS Sequence A435): On the Total Heights in Rooted Labeled Trees

By Shalosh B. Ekhad and Doron Zeilberger

.pdf   .ps   .tex  

(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 "Wn,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 nn-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 (Xn-μ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 .

Maple package

Sample Input and Output Files for the Maple package A435.txt

  • If you want to see explicit expressions for the mean (already done by Riordan and Sloane), variance, and the third through 12th moments about the mean, as well as the limits of the scaled moments up to the 12th

    the input file generates the output file.

  • If you want to see the first 50 terms of the sequences "truncated average", mode, and "truncated median" and the list of Most popular total heights",

    the input file generates the output file.

  • If you want to see pictures of the scaled limiting distribution for N=30,50,100, 150

    See pictures

    Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

    Doron Zeilberger's Home Page