cp's OEIS Frontend

A000014 Number of series-reduced trees with n nodes.

%I A000014 M0320 N0118 #100 Feb 16 2025 08:32:18
%S A000014 0,1,1,0,1,1,2,2,4,5,10,14,26,42,78,132,249,445,842,1561,2988,5671,
%T A000014 10981,21209,41472,81181,160176,316749,629933,1256070,2515169,5049816,
%U A000014 10172638,20543579,41602425,84440886,171794492,350238175,715497037,1464407113
%N A000014 Number of series-reduced trees with n nodes.
%C A000014 Other terms for "series-reduced tree": (i) homeomorphically irreducible tree, (ii) homeomorphically reduced tree, (iii) reduced tree, (iv) topological tree.
%C A000014 In a series-reduced tree, vertices cannot have degree 2; they can be leaves or have >= 2 branches.
%D A000014 F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 284.
%D A000014 D. G. Cantor, personal communication.
%D A000014 F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
%D A000014 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Fig. 3.3.3.
%D A000014 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
%D A000014 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A000014 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A000014 Matthew Parker, <a href="/A000014/b000014.txt">Table of n, a(n) for n = 0..1000</a> (first 501 terms from Christian G. Bower)
%H A000014 David Callan, <a href="http://arxiv.org/abs/1406.7784">A sign-reversing involution to count labeled lone-child-avoiding trees</a>, arXiv:1406.7784 [math.CO], 30 June 2014.
%H A000014 Ira M. Gessel, <a href="https://arxiv.org/abs/2305.03157">Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees</a>, arXiv:2305.03157 [math.CO], 2023.
%H A000014 James Grime and Brady Haran, <a href="http://www.youtube.com/watch?v=iW_LkYiuTKE">The problem in Good Will Hunting</a>, 2013 (Numberphile video).
%H A000014 Frank Harary and Geert Prins, <a href="http://dx.doi.org/10.1007/BF02559543">The number of homeomorphically irreducible trees and other species</a>, Acta Math., 101 (1959), 141-162.
%H A000014 F. Harary, R. W. Robinson and A. J. Schwenk, <a href="http://dx.doi.org/10.1017/S1446788700016190">Twenty-step algorithm for determining the asymptotic number of trees of various species</a>, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
%H A000014 F. Harary, R. W. Robinson and A. J. Schwenk, <a href="http://dx.doi.org/10.1017/S1446788700033760">Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species</a>, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
%H A000014 P. Leroux and B. Miloudi, <a href="/A000081/a000081_2.pdf">Généralisations de la formule d'Otter</a>, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
%H A000014 B. D. McKay, <a href="http://users.cecs.anu.edu.au/~bdm/data/trees.html">Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.</a>
%H A000014 B. D. McKay, <a href="/A000014/a000014.pdf">Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.</a> [Cached copy of top page only, pdf file, no active links, with permission]
%H A000014 Matthew Parker, <a href="https://oeis.org/A000014/a000014_2K.7z">The first 2000 terms (7-Zip compressed file)</a>
%H A000014 A. J. Schwenk, <a href="/A002988/a002988.pdf">Letter to N. J. A. Sloane, Aug 1972</a>
%H A000014 N. J. A. Sloane, <a href="/A000014/a000014.gif">Illustration of initial terms</a>
%H A000014 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 A000014 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 A000014 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Series-ReducedTree.html">Series-Reduced Tree</a>
%H A000014 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A000014 <a href="/index/Cor#core">Index entries for "core" sequences</a>
%F A000014 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 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]
%F A000014 a(n) ~ c * d^n / n^(5/2), where d = A246403 = 2.189461985660850..., c = 0.684447272004914061023163279794145361469033868145768075109924585532604582794... - _Vaclav Kotesovec_, Aug 25 2014
%e A000014 G.f. = x + x^2 + x^4 + x^5 + 2*x^6 + 2*x^7 + 4*x^8 + 5*x^9 + 10*x^10 + ...
%e A000014 The star graph with n nodes (except for n=3) is a series-reduced tree. For n=6 the other series-reduced tree is shaped like the letter H. - _Michael Somos_, Dec 19 2014
%p A000014 with(powseries): with(combstruct): n := 30: Order := n+3: sys := {B = Prod(C,Z), S = Set(B,1 <= card), C = Union(Z,S)}:
%p A000014 G001678 := (convert(gfseries(sys,unlabeled,x) [S(x)], polynom)) * x^2: G0temp := G001678 + x^2:
%p A000014 G059123 := G0temp / x + G0temp - (G0temp^2+eval(G0temp,x=x^2))/(2*x):
%p A000014 G000014 := ((x-1)/x) * G059123 + ((1+x)/x^2) * G0temp - (1/x^2) * G0temp^2:
%p A000014 A000014 := 0,seq(coeff(G000014,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)
%t A000014 a[n_] := If[n<1, 0, A = x/(1-x^2) + x*O[x]^n; For[k=3, k <= n-1, k++, A = A/(1 - x^k + x*O[x]^n)^SeriesCoefficient[A, k]]; s = ((Normal[A] /. x -> x^2) + O[x]^(2n))*(1-x) + A*(2-A)*(1+x); SeriesCoefficient[s, n]/2]; Table[a[n], {n, 0, 40}] (* _Jean-François Alcover_, Feb 02 2016, adapted from PARI *)
%o A000014 (PARI) {a(n) = my(A); if( n<1, 0, A = x / (1 - x^2) + x * O(x^n); for(k=3, n-1, 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 */
%Y A000014 Cf. A000055 (trees), A001678 (series-reduced planted trees), A007827 (series-reduced trees by leaves), A271205 (series-reduced trees by leaves and nodes).
%K A000014 nonn,easy,core,nice
%O A000014 0,7
%A A000014 _N. J. A. Sloane_