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

Dedicated to Neil Sloane and the many contributors to the OEIS. Keep up the good work!

Preface

According to the “brief history”, http://oeis.org/wiki/Welcome#OEIS: Brief History, written

by Neil Sloane himself:

“The sequence database was begun by Neil J. A. Sloane in early 1964 when he was a graduate student at Cornell University in Ithaca, NY. He had encountered a sequence of numbers while working on his dissertation, namely 1, 8, 78, 944, ... (now entry A000435 in the OEIS), and was looking for a formula for the n-th term, in order to determine the rate of growth of the terms.”

That first sequence, now entry http://oeis.org/A000435 in the more than quarter-million sequences strong OEIS [Sl1], is expressible by the formula

(n − 1)! ∑_{k=0}^{n−2} \frac{n^{k}}{k!} .

It appears on page 119 in Sloane’s Ph.D. thesis [Sl2], and in a joint paper with John Riordan [RS], they showed that this is the sum of the the “total heights”, taken over all labeled rooted trees with n vertices, divided by n.

Rooted Labeled Trees

Suppose that you have a society with n individuals, let’s call them 1, …, n, where there is a unique “big boss” (the “root”). Every member of the society, except the big boss, has a unique immediate supervisor. Some people (“leaves”) have no one reporting to them, but the set of immediate subordinates of each supervisor is unordered, i.e. they are considered of equal status in the “pecking order”. Of course, no one can be their own (immediate or indirect) supervisor. How many such hierarchies are possible?

If you draw the hierarchy with a directed edge between any member and his immediate supervisor, you would get a labeled rooted tree. Arthur Cayley[C] famously proved that the number of labeled trees on n vertices is n^{n−2}, hence the number of rooted labeled trees is n · n^{n−2} = n^{n−1}.

There are many proofs of this result, the nicest one is due to André Joyal[J] (see also [LZ]). Another one is using Lagrange Inversion (see [Z1] for a nice exposition), and that’s the one needed for the present article. Let’s review it.

Let r(n) be the number of labeled rooted trees with n vertices, and consider the exponential generating function

R(x) := ∑_{n=0}^{∞} \frac{r(n)}{n!}x^{n} .

If the degree of the root is k, then deleting it gives us a set (i.e. unordered collection) of smaller rooted labeled trees (with disjoint labels), that by general generatingfunctionology has exponential generating function x\frac{R(x)^{k}}{k!} (we divide by k! since the k subtrees are unordered). Summing over all possible k ≥ 0 , we get

R(x) = x ∑_{k=0}^{∞} \frac{R(x)^{k}}{k!} = xe^{R(x)} .

We have just established a functional equation for the formal power series, R(x):

R(x) = xe^{R(x)} .

For any formal power series f(t), let [t^{n}]f(t) denote the coefficient of t^{n} in f(t).

Recall the versatile

Lagrange Inversion Theorem: If R(x) and Φ(z) are formal power series, starting at x and z^{0} respectively, then R(x) = xΦ(R(x)) implies [x^{n}]R(x) = \frac{1}{n}[z^{n−1}]Φ(z)^{n} .

In our case Φ(z) = e^{z}, hence Φ(z)^{n} = e^{nz}, whose coefficient of z^{n−1} is \frac{n^{n−1}}{(n−1)!}. Hence the coefficient of x^{n} in R(x), r(n)/n!, equals

\frac{r(n)}{n!} = \frac{1}{n} · \frac{n^{n−1}}{(n − 1)!} ,

entailing that, indeed,

r(n) = n^{n−1} .

We have just proved that there are exactly n^{n−1} labeled rooted trees with n vertices.

So much for naive counting, but there is a lot of diversity among these hierarchies. One extreme is that everyone, except the big boss, reports directly to the big boss, so the “distance” to the root is always 1 and the sum of the distances is n − 1. There are only n such trees, since once you have chosen the root (the “big boss”) there is nothing to do. This is the most democratic rooted tree.

The other extreme is that the hierarchy is totally ordered. Every vertex has only one subordinate, except the one at the very bottom, that has none. Now the sum of the distances to the root is 0 + 1 + 2 + … + (n − 1) = n(n − 1)/2 (and hence the average distance is (n − 1)/2), and there are n! such trees. Such trees are the most authoritarian, there is a clear ranking, and no one is of equal status.

Hence a natural measure of how “authoritarian” a rooted tree is, is the sum of the heights (distances to the root) taken over all vertices. Let’s define the weight-enumerator of the set of labeled rooted trees on n vertices by

J_{n}(y) := ∑_{T} y^{T otalHeight(T)} ,

where the sum is taken over the set of rooted labeled trees on n vertices. Of course J_{n}(1) = n^{n−1}, but can we we find an explicit expression for J_{n}(y) in terms of n and y? Probably not! Still it would be nice to have an efficient algorithm to generated as many terms of the polynomial sequence {J_{n}(y)} as possible, and also be able to find an explicit expression for J′_{n}(1), since the important quantity “average total height” is given by J′_{n}(1)/n^{n−1}. In fact that was Neil Sloane’s original motivation, that lead to sequence A435.

Weighted Counting According to Total Height

Riordan and Sloane[RS] define the formal power series of the two variables x and y

J(x, y) = ∑_{n=1}^{∞} J_{n}(y)\frac{x^{n}}{n!} ,

that is the exponential generating function of the sequence of polynomials {J_{n}(y)}. Of course J(x, 1) = R(x).

Using the same generatingfunctionology argument, it is not hard to show (as done in [RS]) that J(x, y) satisfies the functional equation

J(x, y) = xe^{J(xy,y)} .  (F E)

Alas, now Lagrange Inversion is no longer applicable, and there is no way to recover J_{n}(y) explicitly.

But what about J_{y}(x, 1)? (i.e. \frac{∂}{∂y} J(x, y) evaluated at y = 1).

Let’s differentiate Eq. (F E) with respect to y, recalling the chain rule from multivariable calculus. We get

J_{y}(x, y) = xe^{J(xy,y)}·\frac{∂}{∂y} J(xy, y) = J(x, y)·\frac{∂}{∂y} J(xy, y) = J(x, y)·(\frac{∂(xy)}{∂y} · \frac{∂}{∂(xy)}J(xy, y) + \frac{∂}{∂y} J(xy, y))

= J(x, y) · (xJ_{x}(xy, y) + J_{y}(xy, y)) .

Now plug-in y = 1 to get

J_{y}(x, 1) = J(x, 1)(xJ_{x}(x, 1) + J_{y}(x, 1)) .

But J(x, 1) is what we called above R(x), and J_{x}(x, 1) is R′(x), hence

J_{y}(x, 1) = xR(x)R′(x) + R(x)J_{y}(x, 1) .

Solving for J_{y}(x, 1) we get

J_{y}(x, 1) = \frac{xR(x)R′(x)}{1 − R(x)} .

It would be nice to express J_{y}(x, 1) in terms of R(x) only, but this is easy.

Differentiating the functional equation R(x) = x e^{R(x)} with respect to x, we get, by the product rule and chain rule (this time Calculus I suffices)

R′(x) = e^{R(x)} + xe^{R(x)}R′(x) = \frac{R(x)}{x} + R(x)R′(x) .

Solving for R′(x) we get

R′(x) = \frac{R(x)}{x(1 − R(x))} .

We note, for the future, that by repeated differentiation (using the quotient rule and the chain rule and repeatedly using that very same equation R′(x) = \frac{R(x)}{x(1−R(x))}) enables us to express any derivative of R(x), R^{(j)}(x), as rational function of R(x) and x with denominator that has the form (1 − R(x))^{2j−1}.

Substituting R′(x) = \frac{R(x)}{x(1−R(x))} into J_{y}(x, 1) = \frac{xR(x)R′(x)}{1−R(x)} gives

J_{y}(x, 1) = \frac{R(x)^{2}}{(1 − R(x))^{2}} .

Now it is time to invoke (see, e.g., [Z1])

The Generalized Lagrange Inversion Theorem: If u(t) and Φ(z) are formal power series starting at t and z^{0} respectively, and G(z) is yet another formal power series, then u(t) = tΦ(u(t)) implies [t^{n}]G(u(t)) = (1/n)[z^{n−1}] G′(z)Φ(z)^{n} .

Here G(z) = \frac{z^{2}}{(1−z)^{2}} and hence G′(z) = 2 \frac{z}{(1−z)^{3}} .

Hence J′_{n}(1)/n!, the coefficient of x^{n} in \frac{R(x)^{2}}{(1−R(x))^{2}} , is 1/n times the coefficient of z^{n−1} in

\frac{2z}{(1 − z)^{3}} · e^{nz} ,

which is the coefficient of z^{n} in

\frac{2z^{2}}{(1 − z)^{3}} · e^{nz} .

But

\frac{2z^{2}}{(1 − z)^{3}} = ∑_{k=0}^{∞}(k − 1)k z^{k} ,

hence \frac{J′_{n}(1)}{n!} is \frac{1}{n} times the coefficient of z^{n} in the formal power series

(∑_{k=0}^{∞}(k − 1)k z^{k}) · (∑_{s=0}^{∞} \frac{n^{s}}{s!} ) .

Hence

\frac{J′_{n}(1)}{n!} = \frac{1}{n} ∑_{k=0}^{n−2} \frac{(n − k − 1)(n − k) n^{k}}{k!} .

Noting that

(n − k)(n − k − 1) = n (n − 1) − 2(n − 1) k + k (k − 1) ,

simple routine algebra leads to

J′_{n}(1) = n! ∑_{k=0}^{n−2} \frac{n^{k}}{k!} .

Hence the average total height among all labeled rooted trees with n vertices is \frac{n!}{n^{n−1}} ∑_{k=0}^{n−2} \frac{n^{k}}{k!} , that we will call W_{n} (please be warned that our notation differs from that of [RS], their W_{n} is n^{n−1} times our W_{n}).

As noted in [RS], W_{n} is asymptotic (thanks to Ramanujan and Watson, see [W]) to n^{3/2}\sqrt{π/2}. We have just reproved, in much more detail than in [RS] (and a somewhat different proof):

Theorem 1 (Riordan-Sloane [RS]) The average total height among all rooted labeled trees on n vertices equals \frac{n!}{n^{n−1}} ∑_{k=0}^{n−2} \frac{n^{k}}{k!} and is asymptotically n^{\frac{3}{2}} \sqrt{π/2}.

Enter Computers

So much can be done by mere humans, but the average is only the most basic statistical information about a random variable. What about the variance? (and hence “coefficient of variation”) skewness? kurtosis? and higher moments? Is there a limiting scaled distribution?

In order to find explicit expressions for higher moments, we need to first find higher factorial moments. The r-th factorial moment is J_{n}^{(r)}(1), and once we know the first r factorial moments we can, by standard theory (see [Z2]), get the moments, and from them, easily, the moments-about-the-mean.

But how can we do that? It turns out that the same method that we described above still works, but very soon gets very tedious for humans. To get the second factorial moment, we have to differentiate (F E) twice, plug-in y = 1 and get an expression for J_{yy}(x, 1) (that is the exponential generating function of J′′_{n}(1),) in terms of R(x), R′(x) and R′′(x). We already noted that each derivative of R(x) can be expressed as rational function of R(x), so at the end it can be expressed in terms of R(x) alone, and we can use the Generalized Lagrange Inversion Formula, as we did above.

Maple knows the chain rule for multi-variable functions, so all this can be done automatically and seamlessly. Also one can teach Maple how to use generalized Lagrange Inversion, and perform all the steps.

All this is implemented in the Maple package A435.txt available from the front of this article

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/a435.html .

Some Computer-Generated Theorems

In the theorems below

W_{n} := \frac{n!}{n^{n−1}} ∑_{k=0}^{n−2} \frac{n^{k}}{k!} .

Recall that Riordan and Sloane showed (and we reproved above) that the average total height among labeled rooted trees with n vertices is W_{n}.

It follows from our algorithm that every moment can always be expressed as some polynomial in n and W_{n}, but they get more and more complicated for higher moments. Below we stae rigorouslyproved explicit expressions for the first four moments, as well as the implied asymptotics and the limits of the α-coefficients, i.e. the limits of the standardized moments. More moments can be found in the output files mentioned later.

Theorem 2. The variance of the random variable “total height” on the set of rooted labeled trees on n vertices is given explicitly by

−W_{n}^{2} − \frac{17}{6} nW_{n} + \frac{5}{3} n^{2}(n − 1) ,

and its asymptotics is (\frac{5}{3} − \frac{π}{2} )n^{3}. Hence the limit of the coefficient of variation (the standarddeviation divided by the mean), as n goes to infinity, is

\frac{\sqrt{2}}{6} \begin{matrix}√ & \overline{−18 π + 60} \\ √ & \overline{π} \end{matrix} = 0.2470484847 ….

Note in particular that there is no “concentration about the mean”.

Theorem 3. The third moment about the mean of the random variable “total height” on the set of rooted labeled trees on n vertices is given explicitly by

2 W_{n}^{3} + \frac{17}{2} nW_{n}^{2} + (−\frac{25}{8} n^{3} + \frac{277}{24} n^{2} − \frac{1}{60} n) W_{n} − \frac{151}{30} n^{4} + \frac{76}{15} n^{3} − \frac{1}{30} n^{2} ,

and its asymptotic expression is

(\frac{1}{2} \sqrt{2}π^{3/2} − \frac{25}{16} \sqrt{2}\sqrt{π}) n^{9/2} ,

that is approximately 0.020795808 n^{9/2}. It follows that the limit of the skewness, as n goes to infinity, is

\frac{(6 π − \frac{75}{4}) \sqrt{3}\sqrt{\frac{π}{10−3 π}}}{10 − 3 π} = .7005665208 ….

In particular we know that the limiting distribution, whatever it is, is not normal. So “total height” defined on rooted labeled trees is not asymptotically normal.

Theorem 4. The fourth moment about the mean of the random variable “total height” on the set of rooted labeled trees on n vertices is given explicitly by

−3 W_{n}^{4} −17 n W_{n}^{3} +(\frac{5}{2} n^{3} − \frac{217}{6} n^{2} + \frac{1}{15} n) W_{n}^{2} +(\frac{649}{80} n^{4} − \frac{74381}{2160} n^{3} + \frac{433}{2520} n^{2} + \frac{1}{105} n) W_{n}

+\frac{221}{63} n^{6} + \frac{4693}{540} n^{5} − \frac{4651}{378} n^{4} + \frac{109}{1260} n^{3} + \frac{2}{105} n^{2} ,

and its asymptotic expression is

(−\frac{3}{4} π^{2} + \frac{5}{4} π + \frac{221}{63}) n^{6} ,

that is approximately 0.032724023n^{6}. It follows that the limit of the kurtosis as n goes to infinity is

\frac{1}{7} \frac{−189 π^{2} + 315 π + 884}{(10 − 3 π)^{2}} = 3.560394751 …,

hence the limiting distribution is leptokurtic.

For theorems about the 5^{th} through the 12^{th} moments we refer the reader to the computer-generated article

http://www.math.rutgers.edu/~zeilberg/tokhniot/oA435a12.txt .

Let us conclude by stating the limits of the scaled moments, α_{k}, for 3 ≤ k ≤ 9.

α_{3} = \frac{(6 π − \frac{75}{4}) \sqrt{3}\sqrt{\frac{π}{10−3 π}}}{10 − 3 π} = .7005665208 …,

α_{4} = \frac{−189 π^{2} + 315 π + 884}{7 (10 − 3 π)^{2}} = 3.560394751 …,

α_{5} = \begin{matrix}(36 π^{2} + \frac{75}{2} π − \frac{105845}{224}) & \sqrt{3} & \sqrt{\frac{π}{10−3 π}} \\ (10 − 3 π) & 2 \end{matrix} = 7.256376376 …,

α_{6} = \frac{15}{16016} \frac{−144144 π^{3} − 720720 π^{2} + 3013725 π + 2120320}{(10 − 3 π)^{3}} = 27.68549546 …,

α_{7} = \begin{matrix}(162 π^{3} + \frac{6615}{4} π^{2} − \frac{103965}{32} π − \frac{101897475}{9152}) & \sqrt{3} & \sqrt{\frac{π}{10−3 π}} \\ (10 − 3 π) & 3 \end{matrix} = 90.01702180 …,

α_{8} = \frac{3}{2586584} \frac{−488864376 π^{4} − 8147739600 π^{3} − 455885430 π^{2} + 86568885375 π + 32820007040}{(10 − 3 π)^{4}}

= 358.8086679 …,

α_{9} = \begin{matrix}(648 π^{4} + 15795 π^{3} + \frac{591867}{16} π^{2} − \frac{461286225}{2288} π − \frac{188411947088175}{662165504}) & \sqrt{3} & \sqrt{\frac{π}{10−3 π}} \\ (10 − 3 π) & 4 \end{matrix} = 1460.710269 ….

For the exact expressions for α_{10}, α_{11}, α_{12} see the output file

http://www.math.rutgers.edu/~zeilberg/tokhniot/oA435a12.txt .

Here are their floating-point approximations:

α_{10} = 6498.233818 …,

α_{11} = 30389.98955 …,
α_{12} = 150516.4157 ….

One of us (DZ) is pledging a donation of one hundred US dollars to the OEIS Foundation, in honor of the first solver(s), for a solution to the following challenge. Challenge: What is the probability density function of the limiting scaled distribution, as n → ∞, of the random variable “total height” defined on the set of labeled rooted trees on n vertices? To get a glimpse of how it is supposed to look like, see the plots here:

http://www.math.rutgers.edu/~zeilberg/tokhniot/oA435c.html .

References

[C] Arthur Cayley, A theorem on trees, Quart. J. Math 23(1889), 376-378.

[J] André Joyal, Une theorie combinatoire des séries formelles, Advances in Mathematics 42(1981), 1-81.

[LZ] Gyu Eun Lee and Doron Zeilberger, Joyal’s Proof of Cayley’s Formula, The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, July 16, 2012. Available on-line from

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/JoyalCayley.html .

[RS] John Riordan and Neil J. A. Sloane, The enumeration of rooted trees by total height, J. Australian Math. Soc. 10(1969), 278-282. Available on line from:

http://neilsloane.com/doc/riordan-enum-trees-by-height.pdf .

[Sl1] Neil J.A. Sloane, “The On-Line Encyclopedia of Integer Sequences”, http://www.oeis.org.

[Sl2] Neil J. A. Sloane, “Lengths of Cycle Times in Random Neural Networks”, Ph.D. Dissertation, Cornell University, February 1967; also Report No. 10, Cognitive Systems Research Program, Cornell University, 1967. Available on-line from

http://neilsloane.com/doc/a000435 OCR.pdf .

[W] George N. Watson, Theorems stated by Ramanujan(V): Approximations connected with e^{x}, Proc. London Math. Soc. (2), 29 (1929), 293-308.

[Z1] Doron Zeilberger, Lagrange Inversion Without Tears (Analysis) (based on Henrici), The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger, 2002. Available on-line from

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/lag.html .

[Z2] Doron Zeilberger, The Automatic Central Limit Theorems Generator (and Much More!) , in: “Advances in Combinatorial Mathematics: Proceedings of the Waterloo Workshop in Computer Algebra 2008 in honor of Georgy P. Egorychev”, chapter 8, pp. 165-174, (I.Kotsireas, E.Zima, eds., Springer Verlag, 2009.) Available on-line from

http://www.math.rutgers.edu/~zeilberg/mamarim/mamarimhtml/georgy.html .

Doron Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

DoronZeil at gmail dot com ; http://www.math.rutgers.edu/~zeilberg/ .

Shalosh B. Ekhad, c/o D. Zeilberger, Department of Mathematics, Rutgers University (New Brunswick), Hill Center-Busch Campus, 110 Frelinghuysen Rd., Piscataway, NJ 08854-8019, USA.

Exclusively published in The Personal Journal of Shalosh B. Ekhad and Doron Zeilberger

( http://www.math.rutgers.edu/~zeilberg/pj.html) and arxiv.org .

Written: July 19, 2016 ;