|
%I #42 Aug 02 2022 09:17:24
%S 1,1,0,1,1,3,3,11,13,47,61,235,341,1301,1983,7741,12650,48629,82826,
%T 317955,564225,2144505,3926353,14828074,27940136,104636890,201837109,
%U 751065460,1479817181,5469566585,10975442036,40330829030,82270184950
%N Number of unlabeled (and unrooted) trees on n nodes having a centroid.
%C Also, number of rooted unlabeled trees on n nodes not having a primary branch.
%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 other hand, define the weight of a node P to be the greatest number of nodes in any subtree connected to P. Then either there is a unique node of minimal weight, the centroid of the tree, or there is a unique pair of minimal weight nodes, the bicentroids.
%C Let T be a tree with root node R. If R and the edges incident with it are deleted, the resulting rooted trees are called branches. A primary branch (there can be at most one) has i nodes where n/2 <= i <= n-1.
%D F. Harary, Graph Theory, Addison-Wesley, Reading, MA, 1994; pp. 35, 36.
%H N. J. A. Sloane, <a href="/A027416/b027416.txt">Table of n, a(n) for n = 0..200</a>
%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 A. Meir and J. W. Moon, <a href="https://doi.org/10.1111/j.1749-6632.1989.tb16423.x">On the branch-sizes of rooted unlabeled trees</a>, in "Graph Theory and Its Applications", Annals New York Acad. Sci., Vol. 576, 1989, pp. 399-407.
%H E. M. Rains and N. J. A. Sloane, <a href="https://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 (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 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F a(n) = A000055(n) - A102911(n/2) if n is even, else a(n) = A000055(n).
%F a(n) = A000081(n) - A027415(n). - _Emeric Deutsch_, Nov 21 2004
%F a(n) = [x^n] 1 + x/Product_{i=1..ceiling(n/2)-1} (1-x^i)^A000081(i). See Cayley link above. - _Geoffrey Critzer_, Jul 30 2022
%p N := 50: Y := [ 1,1 ]: for n from 3 to N do x*mul( (1-x^i)^(-Y[ i ]), i=1..n-1); series(%,x,n+1); b := coeff(%,x,n); Y := [ op(Y),b ]; od: P:=n->sum(Y[n-i]*Y[i],i=1..floor(n/2)): seq(Y[n]-P(n),n=1..35); # _Emeric Deutsch_, Nov 21 2004
%Y Cf. A102911 (trees with a bicentroid), A027415 (trees with a primary branch), A000676 (trees with a center), A000677 (trees with a bicenter), A000055 (trees), A000081 (rooted trees).
%K nonn
%O 0,6
%A _N. J. A. Sloane_
%E More terms from _Emeric Deutsch_, Nov 21 2004
%E Entry revised (with new definition) by _N. J. A. Sloane_, Feb 26 2007
|
