|
%I M0327 N0123 #61 Jan 22 2020 08:55:44
%S 1,1,1,0,2,2,4,6,12,20,39,71,137,261,511,995,1974,3915,7841,15749,
%T 31835,64540,131453,268498,550324,1130899,2330381,4813031,9963288,
%U 20665781,42947715,89410092,186447559,389397778,814447067,1705775653,3577169927
%N Number of series-reduced rooted trees with n nodes.
%C Also known as homeomorphically irreducible rooted trees, or rooted trees without nodes of degree 2.
%C 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
%D D. G. Cantor, personal communication.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Eq. (3.3.9).
%D N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H N. J. A. Sloane, Alois P. Heinz and Vaclav Kotesovec, <a href="/A001679/b001679.txt">Table of n, a(n) for n = 0..1000</a>
%H P. J. Cameron, <a href="http://dx.doi.org/10.1093/qmath/38.2.155">Some treelike objects</a>, Quart. J. Math. Oxford, 38 (1987), 155-183. MR0891613 (89a:05009). See p. 155. - _N. J. A. Sloane_, Apr 18 2014
%H F. Harary, G. Prins, <a href="http://dx.doi.org/10.1007/BF02559543">The number of homeomorphically irreducible trees and other species</a>, Acta Math. 101 (1959) 141-162, W(x,y) equation (9a).
%H N. J. A. Sloane, <a href="/A059123/a059123.jpeg">Illustration of initial terms</a>
%H Eric Weisstein's World of Mathematics, <a href="http://mathworld.wolfram.com/Series-ReducedTree.html">Series-Reduced Tree.</a>
%H Gus Wiseman, <a href="https://docs.google.com/document/d/e/2PACX-1vS1zCO9fgAIe5rGiAhTtlrOTuqsmuPos2zkeFPYB80gNzLb44ufqIqksTB4uM9SIpwlvo-oOHhepywy/pub">Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.</a>
%H <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F 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).
%F a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711... and c = 0.4213018528699249210965028... . - _Vaclav Kotesovec_, Jun 26 2014
%F 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
%e G.f. = 1 + x + x^2 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 12*x^8 + 20*x^9 + ...
%e From _Gus Wiseman_, Jan 21 2020: (Start)
%e 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:
%e o (o) . (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
%e ((oo)) ((ooo)) ((oooo)) ((ooooo)) ((oooooo))
%e (oo(oo)) (oo(ooo)) (oo(oooo))
%e ((o(oo))) (ooo(oo)) (ooo(ooo))
%e ((o(ooo))) (oooo(oo))
%e ((oo(oo))) ((o(oooo)))
%e ((oo(ooo)))
%e ((ooo(oo)))
%e (o(oo)(oo))
%e (oo(o(oo)))
%e (((oo)(oo)))
%e ((o(o(oo))))
%e (End)
%p with(powseries): with(combstruct): n := 30: Order := n+3: sys := {B = Prod(C,Z), S = Set(B,1 <= card), C = Union(Z,S)}:
%p G001678 := (convert(gfseries(sys,unlabeled,x)[S(x)], polynom)) * x^2: G0temp := G001678 + x^2:
%p 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)
%p # adapted for Maple 16 or higher version by _Vaclav Kotesovec_, Jun 26 2014
%t 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}];
%t G[x_] = 1 + ((1 + x)/x)*F[x] - (F[x]^2 + F[x^2])/(2*x) + O[x]^terms;
%t CoefficientList[G[x], x] (* _Jean-François Alcover_, Jan 12 2018 *)
%t urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
%t Table[Length[Select[urt[n],Length[#]!=2&&FreeQ[Z@@#,{_}]&]],{n,15}] (* _Gus Wiseman_, Jan 21 2020 *)
%o (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))};
%Y Apart from initial term, same as A059123.
%Y Cf. A000055 (trees by nodes), A000014 (homeomorphically irreducible trees by nodes), A000669 (homeomorphically irreducible planted trees by leaves), A000081 (rooted trees by nodes).
%Y Cf. A246403.
%Y The labeled version is A060313, with unrooted case A005512.
%Y Matula-Goebel numbers of these trees are given by A331489.
%Y Lone-child-avoiding rooted trees are counted by A001678(n + 1).
%Y Cf. A004111, A060356, A198518, A254382, A291636, A330951, A331488, A331578.
%K nonn
%O 0,5
%A _N. J. A. Sloane_
%E Additional comments from _Michael Somos_, Oct 10 2003
| 