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

 

Logo


Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A001679 Number of series-reduced rooted trees with n nodes.
(Formerly M0327 N0123)
5
1, 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, 3577169927 (list; graph; refs; listen; history; text; internal format)
OFFSET

0,5

COMMENTS

Also known as homeomorphically irreducible rooted trees, or rooted trees without nodes of degree 2.

Prime values begin a(4) = a(5) = 2, a(11) = 71, a(12) = 137, a(18) = 7841, a(19) = 15749, a(29) = 20665781. Semiprime values begin a(6) = 4 = 2^2, a(7) = 6 = 2 * 3, a(10) = 39 = 3 * 13, a(14) = 511 = 7 * 73, a(15) = 995 = 5 * 199, a(20) = 31835 = 5 * 6367, a(26) = 2330381 = 1307 * 1783, a(32) = 186447559 = 2437 * 76507, a(36) = 3577169927 = 41 * 87248047. - Jonathan Vos Post, Jun 18 2005

REFERENCES

Cameron, Peter J. Some treelike objects. Quart. J. Math. Oxford Ser. (2) 38 (1987), no. 150, 155-183. MR0891613 (89a:05009). See p. 155. - N. J. A. Sloane, Apr 18 2014

D. G. Cantor, personal communication.

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

N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).

N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).

LINKS

N. J. A. Sloane, Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..1000

N. J. A. Sloane, Illustration of initial terms

P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183.

F. Harary, G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math. 101 (1959) 141-162, W(x,y) equation (9a)

Eric Weisstein's World of Mathematics, Series-Reduced Tree.

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

FORMULA

G.f. = 1 + ((1+x)*f(x) - (f(x)^2+f(x^2))/2)/x where f(x) is g.f. for A001678 (homeomorphically irreducible planted trees by nodes).

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. = 1 + 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:

G001679 := G0temp / x + G0temp - (G0temp^2+eval(G0temp, x=x^2))/(2*x): A001679 := 0, seq(coeff(G001679, x^i), i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)

MATHEMATICA

terms = 37; (* 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], x] (* Jean-Fran├žois Alcover, 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))};

CROSSREFS

Apart from initial term, same as A059123.

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: A226452 A037163 A059123 * A030435 A063886 A003000

Adjacent sequences:  A001676 A001677 A001678 * A001680 A001681 A001682

KEYWORD

nonn

AUTHOR

N. J. A. Sloane

EXTENSIONS

Additional comments from Michael Somos, Oct 10 2003

Maple program adapted for Maple 16 or higher version by Vaclav Kotesovec, Jun 26 2014

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
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified March 21 22:19 EDT 2019. Contains 321382 sequences. (Running on oeis4.)