login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A027416 Number of unlabeled (and unrooted) trees on n nodes having a centroid. 8

%I

%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

%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_

%Y Cf. A102911 (trees with a bicentroid), A027415 (trees without 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

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

License Agreements, Terms of Use, Privacy Policy. .

Last modified August 4 09:55 EDT 2021. Contains 346446 sequences. (Running on oeis4.)