|
|
A001854
|
|
Total height of all rooted trees on n labeled nodes.
(Formerly M2081 N0822)
|
|
8
|
|
|
0, 2, 15, 148, 1785, 26106, 449701, 8927192, 200847681, 5053782070, 140679853941, 4293235236324, 142553671807729, 5116962926162738, 197459475792232725, 8152354312656732976, 358585728464893234305, 16741214317684425260142, 826842457727306803110997, 43073414675338753123113980
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
|
|
FORMULA
|
|
|
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
|
|
|
KEYWORD
|
nonn
|
|
AUTHOR
|
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|