A000014 - OEIS

%I M0320 N0118 #99 Oct 28 2023 12:01:42

%S 0,1,1,0,1,1,2,2,4,5,10,14,26,42,78,132,249,445,842,1561,2988,5671,

%T 10981,21209,41472,81181,160176,316749,629933,1256070,2515169,5049816,

%U 10172638,20543579,41602425,84440886,171794492,350238175,715497037,1464407113

%N Number of series-reduced trees with n nodes.

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

%C In a series-reduced tree, vertices cannot have degree 2; they can be leaves or have >= 2 branches.

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

%D D. G. Cantor, personal communication.

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

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

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

%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

%H 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 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 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 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 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 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 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 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 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 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 Matthew Parker, <a href="https://oeis.org/A000014/a000014_2K.7z">The first 2000 terms (7-Zip compressed file)</a>

%H A. J. Schwenk, <a href="/A002988/a002988.pdf">Letter to N. J. A. Sloane, Aug 1972</a>

%H N. J. A. Sloane, <a href="/A000014/a000014.gif">Illustration of initial terms</a>

%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 Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Series-ReducedTree.html">Series-Reduced Tree</a>

%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>

%H <a href="/index/Cor#core">Index entries for "core" sequences</a>

%F 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 a(n) ~ c * d^n / n^(5/2), where d = A246403 = 2.189461985660850..., c = 0.684447272004914061023163279794145361469033868145768075109924585532604582794... - _Vaclav Kotesovec_, Aug 25 2014

%e 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 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 with(powseries): with(combstruct): n := 30: Order := n+3: sys := {B = Prod(C,Z), S = Set(B,1 <= card), C = Union(Z,S)}:

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

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

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

%p A000014 := 0,seq(coeff(G000014,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)

%t 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 (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 Cf. A000055 (trees), A001678 (series-reduced planted trees), A007827 (series-reduced trees by leaves), A271205 (series-reduced trees by leaves and nodes).

%K nonn,easy,core,nice

%O 0,7

%A _N. J. A. Sloane_