login
This site is supported by donations to The OEIS Foundation.

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
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. 6
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 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified November 14 16:49 EST 2018. Contains 317210 sequences. (Running on oeis4.)