This site is supported by donations to The OEIS Foundation.



(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001854 Total height of all rooted trees on n labeled nodes
(Formerly M2081 N0822)

%I M2081 N0822

%S 0,2,15,148,1785,26106,449701,8927192,200847681,5053782070,

%T 140679853941,4293235236324,142553671807729,5116962926162738,

%U 197459475792232725,8152354312656732976,358585728464893234305,16741214317684425260142,826842457727306803110997,43073414675338753123113980

%N Total height of all rooted trees on n labeled nodes

%C 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.

%C 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.

%D 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).

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H Alois P. Heinz, <a href="/A001854/b001854.txt">Table of n, a(n) for n = 1..387</a>

%H J. Riordan, <a href="http://dx.doi.org/10.1147/rd.45.0473">Enumeration of trees by height and diameter</a>, IBM J. Res. Dev. 4 (1960), 473-478.

%H J. Riordan, <a href="/A007401/a007401_8.pdf">The enumeration of trees by height and diameter</a>, IBM Journal 4 (1960), 473-478. (Annotated scanned copy)

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%F a(n) = Sum_{k=1..n-1} A034855(n,k)*k. - _Geoffrey Critzer_, Mar 14 2013

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

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

%Y Cf. A000435, A034855, A236396.

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

%K nonn

%O 1,2

%A _N. J. A. Sloane_.

%E More terms from _Geoffrey Critzer_, Mar 14 2013

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified February 24 15:35 EST 2018. Contains 299623 sequences. (Running on oeis4.)