|
| |
|
|
A001679
|
|
Number of series-reduced rooted trees with n nodes.
(Formerly M0327 N0123)
|
|
16
|
|
|
|
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.
A rooted tree is lone-child-avoiding if no vertex has exactly one child, and topologically series-reduced if no vertex has degree 2. This sequence counts unlabeled topologically series-reduced rooted trees with n vertices. Lone-child-avoiding rooted trees with n - 1 vertices are counted by A001678. - Gus Wiseman, Jan 21 2020
|
|
|
REFERENCES
|
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
|
|
|
|
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
For n > 1, this sequence counts lone-child-avoiding rooted trees with n nodes and more than two branches, plus lone-child-avoiding rooted trees with n - 1 nodes. So for n > 1, a(n) = A331488(n) + A001678(n). - Gus Wiseman, Jan 21 2020
|
|
|
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 + ...
The a(1) = 1 through a(8) = 12 unlabeled topologically series-reduced rooted trees with n nodes (empty n = 3 column shown as dot) are:
o (o) . (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
((oo)) ((ooo)) ((oooo)) ((ooooo)) ((oooooo))
(oo(oo)) (oo(ooo)) (oo(oooo))
((o(oo))) (ooo(oo)) (ooo(ooo))
((o(ooo))) (oooo(oo))
((oo(oo))) ((o(oooo)))
((oo(ooo)))
((ooo(oo)))
(o(oo)(oo))
(oo(o(oo)))
(((oo)(oo)))
((o(o(oo))))
(End)
|
|
|
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;
urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]], {ptn, IntegerPartitions[n-1]}];
Table[Length[Select[urt[n], Length[#]!=2&&FreeQ[Z@@#, {_}]&]], {n, 15}] (* Gus Wiseman, Jan 21 2020 *)
|
|
|
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).
Matula-Goebel numbers of these trees are given by A331489.
Lone-child-avoiding rooted trees are counted by A001678(n + 1).
|
|
|
KEYWORD
|
nonn
|
|
|
AUTHOR
|
|
|
|
EXTENSIONS
|
|
|
|
STATUS
|
approved
|
| |
|
|
