A001679 Number of series-reduced rooted trees with n nodes.
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
Offset: 0
Keywords
Examples
G.f. = 1 + x + x^2 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 12*x^8 + 20*x^9 + ...
From _Gus Wiseman_, Jan 21 2020: (Start)
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)
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
- N. J. A. Sloane, Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
- P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155. - _N. J. A. Sloane_, Apr 18 2014
- F. Harary, G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math. 101 (1959) 141-162, W(x,y) equation (9a).
- N. J. A. Sloane, Illustration of initial terms
- Eric Weisstein's World of Mathematics, Series-Reduced Tree.
- Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.
- Index entries for sequences related to rooted trees
- Index entries for sequences related to trees
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.
Matula-Goebel numbers of these trees are given by A331489.
Lone-child-avoiding rooted trees are counted by A001678(n + 1).
Programs
-
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) # adapted for Maple 16 or higher version by Vaclav Kotesovec, Jun 26 2014 -
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 *) 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 *)
-
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))};
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
Extensions
Additional comments from Michael Somos, Oct 10 2003
Comments