A001854 Total height of all rooted trees on n labeled nodes. (Formerly M2081 N0822)

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

Offset

1,2

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

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

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 *)

Crossrefs

Cf. A000435, A034855, A236396.

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

Sequence in context: A253571 A111686 A371582 * A060226 A325060 A002103

Adjacent sequences: A001851 A001852 A001853 * A001855 A001856 A001857

Keyword

nonn

Author

N. J. A. Sloane

Extensions

More terms from Geoffrey Critzer, Mar 14 2013

Status

approved