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

 

Logo

110 people attended OEIS-50 (videos, suggestions); annual fundraising drive to start soon (donate); editors, please edit! (stack is over 300), your editing is more valuable than any donation.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A000014 Number of series-reduced trees with n nodes.
(Formerly M0320 N0118)
23
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 (Numberphile video).

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)].

a(n) ~ c * d^n / n^(5/2), where d = A246403 = 2.189461985660850..., c = 0.684447272004914... . - Vaclav Kotesovec, Aug 25 2014

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 October 31 08:50 EDT 2014. Contains 248861 sequences.