

A000014


Number of seriesreduced 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 "seriesreduced tree": (i) homeomorphically irreducible tree, (ii) homeomorphically reduced tree, (iii) reduced tree, (iv) topological tree.
In a seriesreduced tree, vertices cannot have degree 2; they can be leaves or have >= 2 branches.


REFERENCES

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and TreeLike Structures, Camb. 1998, p. 284.
D. G. Cantor, personal communication.
F. Harary, Graph Theory. AddisonWesley, Reading, MA, 1969, p. 232.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Fig. 3.3.3.
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

Matthew Parker, Table of n, a(n) for n = 0..1000 (first 501 terms from Christian G. Bower).
David Callan, A signreversing involution to count labeled lonechildavoiding trees, arXiv:1406.7784 [math.CO], 30 June 2014.
James Grime and Brady Haran, The problem in Good Will Hunting, 2013 (Numberphile video).
Frank Harary and Geert Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141162.
F. Harary, R. W. Robinson and A. J. Schwenk, Twentystep algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483503.
F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twentystep algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 5380, 1992. (Annotated scanned copy)
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes. [Cached copy of top page only, pdf file, no active links, with permission]
Matthew Parker, The first 2000 terms (7Zip compressed file)
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
N. J. A. Sloane, Illustration of initial terms
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, SeriesReduced Tree
Index entries for sequences related to trees
Index entries for "core" sequences


FORMULA

G.f.: A(x) = ((x1)/x)*f(x) + ((1+x)/x^2)*g(x)  (1/x^2)*g(x)^2 where f(x) is g.f. for A059123 and 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)]. [corrected by Wolfdieter Lang, Jan 09 2001]
a(n) ~ c * d^n / n^(5/2), where d = A246403 = 2.189461985660850..., c = 0.684447272004914061023163279794145361469033868145768075109924585532604582794...  Vaclav Kotesovec, Aug 25 2014


EXAMPLE

G.f. = x + x^2 + x^4 + x^5 + 2*x^6 + 2*x^7 + 4*x^8 + 5*x^9 + 10*x^10 + ...
The star graph with n nodes (except for n=3) is a seriesreduced tree. For n=6 the other seriesreduced tree is shaped like the letter H.  Michael Somos, Dec 19 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 := ((x1)/x) * G059123 + ((1+x)/x^2) * G0temp  (1/x^2) * G0temp^2:
A000014 := 0, seq(coeff(G000014, x^i), i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)


MATHEMATICA

a[n_] := If[n<1, 0, A = x/(1x^2) + x*O[x]^n; For[k=3, k <= n1, k++, A = A/(1  x^k + x*O[x]^n)^SeriesCoefficient[A, k]]; s = ((Normal[A] /. x > x^2) + O[x]^(2n))*(1x) + A*(2A)*(1+x); SeriesCoefficient[s, n]/2]; Table[a[n], {n, 0, 40}] (* JeanFrançois Alcover, Feb 02 2016, adapted from PARI *)


PROG

(PARI) {a(n) = my(A); if( n<1, 0, A = x / (1  x^2) + x * O(x^n); for(k=3, n1, A /= (1  x^k + x * O(x^n))^polcoeff(A, k)); polcoeff( (subst(A, x, x^2) * (1  x) + A * (2  A) * (1 + x)) / 2, n))}; /* Michael Somos, Dec 19 2014 */


CROSSREFS

Cf. A000055 (trees), A001678 (seriesreduced planted trees), A007827 (seriesreduced trees by leaves), A271205 (seriesreduced trees by leaves and nodes).
Sequence in context: A305840 A178113 A032090 * A114851 A099364 A125951
Adjacent sequences: A000011 A000012 A000013 * A000015 A000016 A000017


KEYWORD

nonn,easy,core,nice


AUTHOR

N. J. A. Sloane


STATUS

approved



