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.

0, 1, 1, 0, 2, 2, 4, 6, 12, 20, 39, 71, 137, 261, 511, 995, 1974, 3915, 7841, 15749, 31835, 64540, 131453, 268498, 550324, 1130899, 2330381, 4813031, 9963288, 20665781, 42947715, 89410092, 186447559, 389397778, 814447067, 1705775653

Offset: 0

Author

Wolfdieter Lang, Jan 09 2001

Keywords

• nonn
• easy
• nice

Comments

Essentially the same as A001679. - Eric W. Weisstein, Mar 25 2022

Examples

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

References

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

Links

• N. J. A. Sloane, Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
• David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)
• P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183.
• N. J. A. Sloane, Illustration of initial terms
• Index entries for sequences related to trees
• Index entries for sequences related to rooted trees

Crossrefs

Cf. A001679.

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

Cf. A246403.

Programs

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

Mathematica

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}];
G[x_] = 1 + ((1 + x)/x)*F[x] - (F[x]^2 + F[x^2])/(2*x) + O[x]^terms;
CoefficientList[G[x] - 1, x] (* Jean-François Alcover, May 25 2012, updated Jan 12 2018 *)

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 */

Formula

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).

a(n) = A001679(n) if n>0. - Michael Somos, Jun 13 2014

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