login
Number of centered trees with n nodes.
(Formerly M0831 N0316)
13

%I M0831 N0316 #54 Dec 21 2022 20:16:59

%S 1,1,0,1,1,2,3,7,12,27,55,127,284,682,1618,3979,9823,24722,62651,

%T 160744,415146,1081107,2831730,7462542,19764010,52599053,140580206,

%U 377244482,1016022191,2745783463,7443742141,20239038700,55178647926,150820588425,413226000775

%N Number of centered trees with n nodes.

%C A tree has either a center or a bicenter and either a centroid or a bicentroid. (These terms were introduced by Jordan.)

%C If the number of edges in a longest path in the tree is 2m, then the middle node in the path is the unique center, otherwise the two middle nodes in the path are the unique bicenters.

%C On the bottom of first page 266 of article Cayley (1881) is a table of A000676 and A000677 for n = 1..13. - _Michael Somos_, Aug 20 2018

%D N. L. Biggs et al., Graph Theory 1736-1936, Oxford, 1976, p. 49.

%D F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994; pp. 35, 36.

%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 Geoffrey Critzer, <a href="/A000676/b000676.txt">Table of n, a(n) for n = 0..200</a> (replacing the first version from N. J. A. Sloane)

%H Jean-François Alcover, <a href="/A000676/a000676.txt">Mathematica program</a>

%H A. Cayley, <a href="http://dx.doi.org/10.1017/CBO9780511703751.056">On the analytical forms called trees, with application to the theory of chemical combinations</a>, Reports British Assoc. Advance. Sci. 45 (1875), 257-305 = Math. Papers, Vol. 9, 427-460 (see p. 438).

%H A. Cayley, <a href="http://www.jstor.org/stable/2369158">On the analytical forms called trees</a>, Amer. J. Math., 4 (1881), 266-268.

%H C. Jordan, <a href="http://www.digizeitschriften.de/dms/resolveppn/?PID=GDZPPN002153998">Sur les assemblages des lignes</a>, J. Reine angew. Math., 70 (1869), 185-190.

%H E. M. Rains and N. J. A. Sloane, <a href="http://www.cs.uwaterloo.ca/journals/JIS/cayley.html">On Cayley's Enumeration of Alkanes (or 4-Valent Trees)</a>, J. Integer Sequences, Vol. 2 (1999), Article 99.1.1. [This articles states incorrectly that A000676 and A000677 give the numbers of trees with respectively a centroid and bicentroid.]

%H Peter Steinbach, <a href="/A000088/a000088_17.pdf">Field Guide to Simple Graphs, Volume 1</a>, Part 17 [but beware errors] (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Peter Steinbach, <a href="/A000055/a000055_12.pdf">Field Guide to Simple Graphs, Volume 3</a>, Part 12 [but beware errors] (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)

%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/CenteredTree.html">Centered Tree</a>.

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

%F a(n) + A000677(n) = A000055(n).

%e G.f. = 1 + x + x^3 + x^4 + 2*x^5 + 3*x^6 + 7*x^7 + 12*x^8 + 27*x^9 + 55*x^10 + ... - _Michael Somos_, Aug 20 2018

%t See link.

%Y Cf. A102911 (trees with a bicentroid), A027416 (trees with a centroid), A000677 (trees with a bicenter), A000055 (trees), A000081 (rooted trees).

%K nonn,nice,easy

%O 0,6

%A _N. J. A. Sloane_