login
This site is supported by donations to The OEIS Foundation.

 

Logo

The OEIS is looking to hire part-time people to help edit core sequences, upload scanned documents, process citations, fix broken links, etc. - Neil Sloane, njasloane@gmail.com

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001854 Total height of all rooted trees on n labeled nodes
(Formerly M2081 N0822)
7
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

Alois P. Heinz, Table of n, a(n) for n = 1..100

J. Riordan, Enumeration of trees by height and diameter, IBM J. Res. Dev. 4 (1960), 473-478.

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: A224885 A253571 A111686 * A060226 A002103 A191364

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

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 May 26 22:52 EDT 2017. Contains 287181 sequences.