cp's OEIS Frontend

A059123 Number of homeomorphically irreducible rooted trees (also known as series-reduced rooted trees, or rooted trees without nodes of degree 2) with n >= 1 nodes.

%I A059123 #37 Apr 04 2022 10:15:15
%S A059123 0,1,1,0,2,2,4,6,12,20,39,71,137,261,511,995,1974,3915,7841,15749,
%T A059123 31835,64540,131453,268498,550324,1130899,2330381,4813031,9963288,
%U A059123 20665781,42947715,89410092,186447559,389397778,814447067,1705775653
%N A059123 Number of homeomorphically irreducible rooted trees (also known as series-reduced rooted trees, or rooted trees without nodes of degree 2) with n >= 1 nodes.
%C A059123 Essentially the same as A001679. - _Eric W. Weisstein_, Mar 25 2022
%D A059123 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Eq. (3.3.9).
%H A059123 N. J. A. Sloane, Alois P. Heinz and Vaclav Kotesovec, <a href="/A059123/b059123.txt">Table of n, a(n) for n = 0..1000</a>
%H A059123 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 A059123 P. J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183.
%H A059123 N. J. A. Sloane, <a href="/A059123/a059123.jpeg">Illustration of initial terms</a>
%H A059123 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%H A059123 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%F A059123 G.f.: 1 + ((1+x)/x)*f(x) - (f(x)^2+f(x^2))/(2*x) where 1+f(x) is g.f. for A001678 (homeomorphically irreducible planted trees by nodes).
%F A059123 a(n) = A001679(n) if n>0. - _Michael Somos_, Jun 13 2014
%F A059123 a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711... and c = 0.421301852869924921096502830935802411658488216342994235732491571594804013... - _Vaclav Kotesovec_, Jun 26 2014
%e A059123 G.f. = x + x^2 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 12*x^8 + 20*x^9 + ...
%p A059123 with(powseries): with(combstruct): n := 30: Order := n+3: sys := {B = Prod(C,Z), S = Set(B,1 <= card), C = Union(Z,S)}:
%p A059123 G001678 := (convert(gfseries(sys,unlabeled,x)[S(x)], polynom)) * x^2: G0temp := G001678 + x^2:
%p A059123 G059123 := G0temp / x + G0temp - (G0temp^2+eval(G0temp,x=x^2))/(2*x): A059123 := 0,seq(coeff(G059123,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)
%t A059123 terms = 36; (* F = G001678 *) F[_] = 0; Do[F[x_] = (x^2/(1 + x))*Exp[Sum[ F[x^k]/(k*x^k), {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms + 1}];
%t A059123 G[x_] = 1 + ((1 + x)/x)*F[x] - (F[x]^2 + F[x^2])/(2*x) + O[x]^terms;
%t A059123 CoefficientList[G[x] - 1, x] (* _Jean-François Alcover_, May 25 2012, updated Jan 12 2018 *)
%o A059123 (PARI) {a(n) = local(A); if( n<3, n>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( (1 + x) * A - x * (A^2 + subst(A, x, x^2)) / 2, n))}; /* _Michael Somos_, Jun 13 2014 */
%Y A059123 Cf. A001679.
%Y A059123 Cf. A000055 (trees by nodes), A000014 (homeomorphically irreducible trees by nodes), A000669 (homeomorphically irreducible planted trees by leaves), A000081 (rooted trees by nodes).
%Y A059123 Cf. A246403.
%K A059123 nonn,easy,nice
%O A059123 0,5
%A A059123 _Wolfdieter Lang_, Jan 09 2001