|
| |
|
|
A001679
|
|
Number of series-reduced rooted trees with n nodes.
(Formerly M0327 N0123)
|
|
3
| |
|
|
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; 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 (jvospost3(AT)gmail.com), Jun 18 2005
|
|
|
REFERENCES
| D. G. Cantor, personal communication.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Eq. (3.3.9).
F. Harary and G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
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, Table of n, a(n) for n = 0..500
N. J. A. Sloane, Illustration of initial terms
Eric Weisstein's World of Mathematics, Link to a section of The World of Mathematics.
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).
|
|
|
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); # from UlrSchimke(AT)aol.com
|
|
|
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).
Sequence in context: A028408 A037163 A059123 * A030435 A063886 A003000
Adjacent sequences: A001676 A001677 A001678 * A001680 A001681 A001682
|
|
|
KEYWORD
| nonn
|
|
|
AUTHOR
| N. J. A. Sloane (njas(AT)research.att.com).
|
|
|
EXTENSIONS
| Additional comments from Michael Somos, Oct 10, 2003
|
| |
|
|
