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

 

Logo

Invitation: celebrating 50 years of OEIS, 250000 sequences, and Sloane's 75th, there will be a conference at DIMACS, Rutgers, Oct 9-10 2014.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000014 Number of series-reduced trees with n nodes.
(Formerly M0320 N0118)
22
0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26, 42, 78, 132, 249, 445, 842, 1561, 2988, 5671, 10981, 21209, 41472, 81181, 160176, 316749, 629933, 1256070, 2515169, 5049816, 10172638, 20543579, 41602425, 84440886, 171794492, 350238175, 715497037, 1464407113 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,7

COMMENTS

Other terms for "series-reduced tree": (i) homeomorphically irreducible tree, (ii) homeomorphically reduced tree, (iii) reduced tree, (iv) topological tree.

REFERENCES

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 284.

D. G. Cantor, personal communication.

F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Fig. 3.3.3.

F. Harary and G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.

F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503. Errata: Vol. A 41 (1986), p. 325.

J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.

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

Christian G. Bower, Table of n, a(n) for n = 0..500

David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)

James Grime and Brady Haran, The problem in Good Will Hunting, 2013.

N. J. A. Sloane, Illustration of initial terms

Eric Weisstein's World of Mathematics, Series-Reduced Tree

Index entries for sequences related to trees

Index entries for "core" sequences

FORMULA

G.f.: A(x) = ((x-1)/x)*f(x) + ((1+x)/x^2)*g(x) - (1/x^2)*g(x)^2 where f(x) is g.f. for A059123 and 1+g(x) is g.f. for A001678. [Harary and E. M. Palmer, p. 62, Eq. (3.3.10) with extra -(1/x^2)*Hbar(x)^2 term which should be there according to eq.(3.3.14), p. 63, with eq.(3.3.9)].

MAPLE

with (powseries): with (combstruct): n := 30: Order := n+3: sys := {B = Prod(C, Z), S = Set(B, 1 <= card), C = Union(Z, S)}:

G001678 := (convert(gfseries(sys, unlabeled, x) [S(x)], polynom)) * x^2: G0temp := G001678 + x^2:

G059123 := G0temp / x + G0temp - (G0temp^2+eval(G0temp, x=x^2))/(2*x):

G000014 := ((x-1)/x) * G059123 + ((1+x)/x^2) * G0temp - (1/x^2) * G0temp^2:

A000014 := 0, seq(coeff(G000014, x^i), i=1..n); # from UlrSchimke(AT)aol.com

CROSSREFS

Cf. A000055 (trees), A001678 (series-reduced planted trees), A007827 (series-reduced trees by leaves).

Sequence in context: A127712 A178113 A032090 * A114851 A099364 A125951

Adjacent sequences:  A000011 A000012 A000013 * A000015 A000016 A000017

KEYWORD

nonn,easy,core,nice

AUTHOR

N. J. A. Sloane.

EXTENSIONS

G.f. corrected by Wolfdieter Lang, Jan 09 2001.

STATUS

approved

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

Content is available under The OEIS End-User License Agreement .

Last modified July 31 03:18 EDT 2014. Contains 245079 sequences.