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,5

Comments

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

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

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

Example

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

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

Prog

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

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.

Sequence in context: A028408 A226452 A037163 * A001679 A030435 A063886

Adjacent sequences: A059120 A059121 A059122 * A059124 A059125 A059126

Keyword

nonn,easy,nice

Author

Wolfdieter Lang, Jan 09 2001

Status

approved