A001854 Total height of all rooted trees on n labeled nodes.

0, 2, 15, 148, 1785, 26106, 449701, 8927192, 200847681, 5053782070, 140679853941, 4293235236324, 142553671807729, 5116962926162738, 197459475792232725, 8152354312656732976, 358585728464893234305, 16741214317684425260142, 826842457727306803110997, 43073414675338753123113980

Offset: 1

Author

N. J. A. Sloane

Keywords

• nonn

Comments

Take any one of the n^(n-1) rooted trees on n labeled nodes, compute its height (maximal edge distance to root), sum over all trees.

Theorem [Renyi-Szekeres, (4,7)]. The average height if the tree is chosen at random is sqrt(2*n*Pi). - David desJardins, Jan 20 2017

References

• Rényi, A., and G. Szekeres. "On the height of trees." Journal of the Australian Mathematical Society 7.04 (1967): 497-507. See (4.7).
• N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
• N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

Links

• Alois P. Heinz, Table of n, a(n) for n = 1..387
• J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.
• J. Riordan, The enumeration of trees by height and diameter, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)
• Index entries for sequences related to trees

Crossrefs

Cf. A000435, A034855, A236396.

Also A234953(n) = a(n)/n.

Programs

Mathematica

nn=20;a=NestList[ x Exp[#]&,x,nn];f[list_]:=Sum[list[[i]]*i,{i,1,Length[list]}];Drop[Map[f,Transpose[Table[Range[0,nn]!CoefficientList[Series[a[[i+1]]-a[[i]],{x,0,nn}],x],{i,1,nn-1}]]],1]  (* Geoffrey Critzer, Mar 14 2013 *)

Formula

a(n) = Sum_{k=1..n-1} A034855(n,k)*k. - Geoffrey Critzer, Mar 14 2013

A000435(n)/a(n) ~ 1/2 (see A000435 and the Renyi-Szekeres result mentioned in the Comments). - David desJardins, Jan 20 2017

Extensions

More terms from Geoffrey Critzer, Mar 14 2013