[go: up one dir, main page]

login

Year-end appeal: Please make a donation to the OEIS Foundation to support ongoing development and maintenance of the OEIS. We are now in our 61st year, we have over 378,000 sequences, and we’ve reached 11,000 citations (which often say “discovered thanks to the OEIS”).

Number of series-reduced planted trees with n nodes.
(Formerly M0768 N0293)
145

%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