A059123 - OEIS

%I #37 Apr 04 2022 10:15:15

%S 0,1,1,0,2,2,4,6,12,20,39,71,137,261,511,995,1974,3915,7841,15749,

%T 31835,64540,131453,268498,550324,1130899,2330381,4813031,9963288,

%U 20665781,42947715,89410092,186447559,389397778,814447067,1705775653

%N 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 Essentially the same as A001679. - _Eric W. Weisstein_, Mar 25 2022

%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Eq. (3.3.9).

%H 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 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 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 N. J. A. Sloane, <a href="/A059123/a059123.jpeg">Illustration of initial terms</a>

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

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

%F 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 a(n) = A001679(n) if n>0. - _Michael Somos_, Jun 13 2014

%F a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711... and c = 0.421301852869924921096502830935802411658488216342994235732491571594804013... - _Vaclav Kotesovec_, Jun 26 2014

%e G.f. = x + x^2 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 12*x^8 + 20*x^9 + ...

%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): A059123 := 0,seq(coeff(G059123,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)

%t 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 G[x_] = 1 + ((1 + x)/x)*F[x] - (F[x]^2 + F[x^2])/(2*x) + O[x]^terms;

%t CoefficientList[G[x] - 1, x] (* _Jean-François Alcover_, May 25 2012, updated Jan 12 2018 *)

%o (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 Cf. A001679.

%Y Cf. A000055 (trees by nodes), A000014 (homeomorphically irreducible trees by nodes), A000669 (homeomorphically irreducible planted trees by leaves), A000081 (rooted trees by nodes).

%Y Cf. A246403.

%K nonn,easy,nice

%O 0,5

%A _Wolfdieter Lang_, Jan 09 2001