|
%I M0768 N0293 #101 Oct 27 2023 19:28:34
%S 0,0,1,0,1,1,2,3,6,10,19,35,67,127,248,482,952,1885,3765,7546,15221,
%T 30802,62620,127702,261335,536278,1103600,2276499,4706985,9752585,
%U 20247033,42110393,87733197,183074638,382599946,800701320,1677922740,3520581954
%N Number of series-reduced planted trees with n nodes.
%C The initial term is 0 by convention, though a good case can be made that it should be 1 instead.
%C Series-reduced trees contain no node with valency 2; see A000014 for the unrooted series-reduced trees. - _Joerg Arndt_, Mar 03 2015
%C For n>=2, a(n+1) is the number of unordered rooted trees (see A000081) with n nodes where nodes cannot have out-degree 1, see example. Imposing the condition only at non-root nodes gives A198518. - _Joerg Arndt_, Jun 28 2014
%C For n>=3, a(n+1) is the number of unordered rooted trees with n nodes where all limbs are of length >= 2. Limbs are the paths from the leafs (towards the root) to the nearest branching point (with the root considered to be a branching point). - _Joerg Arndt_, Mar 03 2015
%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 lone-child-avoiding rooted trees with n - 1 vertices. Topologically series-reduced rooted trees are counted by A001679, which is essentially the same as A059123. - _Gus Wiseman_, Jan 20 2020
%D D. G. Cantor, personal communication.
%D J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 525.
%D F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62.
%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 Alois P. Heinz, <a href="/A001678/b001678.txt">Table of n, a(n) for n = 0..1000</a> (first 501 terms from Christian G. Bower)
%H David Callan, <a href="http://arxiv.org/abs/1406.7784">A sign-reversing involution to count labeled lone-child-avoiding trees</a>, arXiv:1406.7784 [math.CO], (30-June-2014).
%H F. Harary and E. M. Palmer, <a href="http://dx.doi.org/10.1017/S0305004100055857">Probability that a point of a tree is fixed</a>, Math. Proc. Camb. Phil. Soc. 85 (1979) 407-415.
%H F. Harary and 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.
%H F. Harary, R. W. Robinson and A. J. Schwenk, <a href="http://dx.doi.org/10.1017/S1446788700016190">Twenty-step algorithm for determining the asymptotic number of trees of various species</a>, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
%H F. Harary, R. W. Robinson and A. J. Schwenk, <a href="http://dx.doi.org/10.1017/S1446788700033760">Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species</a>, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
%H INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=404">Encyclopedia of Combinatorial Structures 404</a>
%H Marko Riedel, <a href="https://math.stackexchange.com/questions/4080821/">Generating functions of unordered rooted trees with n nodes where nodes cannot have out-degree 1, classified by the number of leaves, using the Polya Enumeration Theorem and the exponential formula</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="/A001678/a001678.txt">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.: A(x) satisfies A(x) = (x^2/(1+x))*exp( Sum_{k>=1} A(x^k)/(k*x^k) ) [Harary and E. M. Palmer, 1973, p. 62, Eq. (3.3.8)].
%F G.f.: A(x) = Sum_{n>=2} a(n) * x^n = x^2 / ((1 + x) * Product_{k>0} (1 - x^k)^a(k+1)). - _Michael Somos_, Oct 06 2003
%F a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.189461985660850563... and c = 0.1924225474701550354144525345664845514828912790855223729854471406053655209... - _Vaclav Kotesovec_, Jun 26 2014
%F a(n) = Sum_{i=2..n-2} A106179(i, n-1-i) for n >= 3. - _Andrew Howroyd_, Mar 29 2021
%e --------------- Examples (i=internal,e=external): ---------------------------
%e |.n=2.|..n=4..|..n=5..|...n=6.............|....n=7..........................|
%e |.....|.......|.......|.............e...e.|................e.e.e......e...e.|
%e |.....|.e...e.|.e.e.e.|.e.e.e.e...e...i...|.e.e.e.e.e...e....i....e.e...i...|
%e |..e..|...i...|...i...|....i........i.....|.....i..........i..........i.....|
%e |..e..|...e...|...e...|....e........e.....|.....e..........e..........e.....|
%e -----------------------------------------------------------------------------
%e G.f. = x^2 + x^4 + x^5 + 2*x^6 + 3*x^7 + 6*x^8 + 10*x^9 + 19*x^10 + ...
%e From _Joerg Arndt_, Jun 28 2014: (Start)
%e The a(8) = 6 rooted trees with 7 nodes as described in the comment are:
%e : level sequence out-degrees (dots for zeros)
%e : 1: [ 0 1 2 3 3 2 1 ] [ 2 2 2 . . . . ]
%e : O--o--o--o
%e : .--o
%e : .--o
%e : .--o
%e :
%e : 2: [ 0 1 2 2 2 2 1 ] [ 2 4 . . . . . ]
%e : O--o--o
%e : .--o
%e : .--o
%e : .--o
%e : .--o
%e :
%e : 3: [ 0 1 2 2 2 1 1 ] [ 3 3 . . . . . ]
%e : O--o--o
%e : .--o
%e : .--o
%e : .--o
%e : .--o
%e :
%e : 4: [ 0 1 2 2 1 2 2 ] [ 2 2 . . 2 . . ]
%e : O--o--o
%e : .--o
%e : .--o--o
%e : .--o
%e :
%e : 5: [ 0 1 2 2 1 1 1 ] [ 4 2 . . . . . ]
%e : O--o--o
%e : .--o
%e : .--o
%e : .--o
%e : .--o
%e :
%e : 6: [ 0 1 1 1 1 1 1 ] [ 6 . . . . . . ]
%e : O--o
%e : .--o
%e : .--o
%e : .--o
%e : .--o
%e : .--o
%e :
%e (End)
%e From _Gus Wiseman_, Jan 20 2020: (Start)
%e The a(2) = 1 through a(9) = 10 unlabeled lone-child-avoiding rooted trees with n - 1 nodes (empty n = 3 column shown as dot) are:
%e o . (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
%e (o(oo)) (o(ooo)) (o(oooo)) (o(ooooo))
%e (oo(oo)) (oo(ooo)) (oo(oooo))
%e (ooo(oo)) (ooo(ooo))
%e ((oo)(oo)) (oooo(oo))
%e (o(o(oo))) ((oo)(ooo))
%e (o(o(ooo)))
%e (o(oo)(oo))
%e (o(oo(oo)))
%e (oo(o(oo)))
%e (End)
%p with (powseries): with (combstruct): n := 30: sys := {B = Prod(C,Z), S = Set(B,1 <= card), C = Union(Z,S)}: A001678 := 1,0,1,seq(count([S, sys, unlabeled],size=i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)
%p # second Maple program:
%p with(numtheory):
%p b:= proc(n) option remember; `if`(n=0, 1, add(add(
%p d*a(d+1), d=divisors(j))*b(n-j), j=1..n)/n)
%p end:
%p a:= proc(n) option remember; `if`(n<2, 0,
%p `if`(n=2, 1, b(n-2)-a(n-1)))
%p end:
%p seq(a(n), n=0..50); # _Alois P. Heinz_, Jul 02 2014
%t b[n_] := b[n] = If[n == 0, 1, Sum[Sum[d*a[d+1], {d, Divisors[j]}]*b[n-j], {j, 1, n}]/n]; a[n_] := a[n] = If[n < 2, 0, If[n == 2, 1, b[n-2] - a[n-1]]]; Table[a[n], {n, 0, 50}] (* _Jean-François Alcover_, Sep 24 2014, after _Alois P. Heinz_ *)
%t terms = 38; A[_] = 0; Do[A[x_] = (x^2/(1+x))*Exp[Sum[A[x^k]/(k*x^k), {k, 1, j}]] + O[x]^j // Normal, {j, 1, terms}]; CoefficientList[A[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[If[n<=1,0,Length[Select[urt[n-1],FreeQ[#,{_}]&]]],{n,0,10}] (* _Gus Wiseman_, Jan 20 2020 *)
%o (PARI) (a(n) = if( n<4, n==2, T(n-2, n-3))); /* where */ {T(n, k) = if( n<1 || k<1, (n==0) && (k>=0), sum(j=1, k, sum(i=1, n\j, T(n-i*j, min(n-i*j, j-1)) * binomial( a(j+1) + i-1, i))))}; /* _Michael Somos_, Jun 04 2002 */
%o (PARI) {a(n) = local(A); if( n<3, n==2, A = x / (1 - x^2) + O(x^n); for(k=3, n-2, A /= (1 - x^k + O(x^n))^polcoeff(A, k)); polcoeff(A, n-1))}; /* _Michael Somos_, Oct 06 2003 */
%Y Cf. A000014, A007827, A246403, A005202.
%Y Unlabeled rooted trees are counted by A000081.
%Y Topologically series-reduced rooted trees are counted by A001679.
%Y Labeled lone-child-avoiding rooted trees are counted by A060356.
%Y Labeled lone-child-avoiding unrooted trees are counted by A108919.
%Y Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
%Y Singleton-reduced rooted trees are counted by A330951.
%Y Cf. A000669, A004111, A106179, A198518, A254382, A331488, A331578.
%K nonn,easy,nice
%O 0,7
%A _N. J. A. Sloane_
%E Additional comments from _Michael Somos_, Jun 05 2002
| 