This is a front-end for the Online Encyclopedia of Integer Sequences, made by Christian Perfect. The idea is to provide OEIS entries in non-ancient HTML, and then to think about how they're presented visually. The source code is on GitHub.
%I A001678 M0768 N0293 #102 Feb 16 2025 08:32:24
%S A001678 0,0,1,0,1,1,2,3,6,10,19,35,67,127,248,482,952,1885,3765,7546,15221,
%T A001678 30802,62620,127702,261335,536278,1103600,2276499,4706985,9752585,
%U A001678 20247033,42110393,87733197,183074638,382599946,800701320,1677922740,3520581954
%N A001678 Number of series-reduced planted trees with n nodes.
%C A001678 The initial term is 0 by convention, though a good case can be made that it should be 1 instead.
%C A001678 Series-reduced trees contain no node with valency 2; see A000014 for the unrooted series-reduced trees. - _Joerg Arndt_, Mar 03 2015
%C A001678 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 A001678 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 A001678 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 A001678 D. G. Cantor, personal communication.
%D A001678 J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 525.
%D A001678 F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62.
%D A001678 N. J. A. Sloane, A Handbook of Integer Sequences, Academic Press, 1973 (includes this sequence).
%D A001678 N. J. A. Sloane and Simon Plouffe, The Encyclopedia of Integer Sequences, Academic Press, 1995 (includes this sequence).
%H A001678 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 A001678 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 A001678 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 A001678 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 A001678 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 A001678 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 A001678 INRIA Algorithms Project, <a href="http://ecs.inria.fr/services/structure?nbr=404">Encyclopedia of Combinatorial Structures 404</a>
%H A001678 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 A001678 Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/Series-ReducedTree.html">Series-reduced tree.</a>
%H A001678 Gus Wiseman, <a href="/A001678/a001678.txt">Sequences counting series-reduced and lone-child-avoiding trees by number of vertices</a>.
%H A001678 <a href="/index/Ro#rooted">Index entries for sequences related to rooted trees</a>
%H A001678 <a href="/index/Tra#trees">Index entries for sequences related to trees</a>
%F A001678 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 A001678 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 A001678 a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.189461985660850563... and c = 0.1924225474701550354144525345664845514828912790855223729854471406053655209... - _Vaclav Kotesovec_, Jun 26 2014
%F A001678 a(n) = Sum_{i=2..n-2} A106179(i, n-1-i) for n >= 3. - _Andrew Howroyd_, Mar 29 2021
%e A001678 --------------- Examples (i=internal,e=external): ---------------------------
%e A001678 |.n=2.|..n=4..|..n=5..|...n=6.............|....n=7..........................|
%e A001678 |.....|.......|.......|.............e...e.|................e.e.e......e...e.|
%e A001678 |.....|.e...e.|.e.e.e.|.e.e.e.e...e...i...|.e.e.e.e.e...e....i....e.e...i...|
%e A001678 |..e..|...i...|...i...|....i........i.....|.....i..........i..........i.....|
%e A001678 |..e..|...e...|...e...|....e........e.....|.....e..........e..........e.....|
%e A001678 -----------------------------------------------------------------------------
%e A001678 G.f. = x^2 + x^4 + x^5 + 2*x^6 + 3*x^7 + 6*x^8 + 10*x^9 + 19*x^10 + ...
%e A001678 From _Joerg Arndt_, Jun 28 2014: (Start)
%e A001678 The a(8) = 6 rooted trees with 7 nodes as described in the comment are:
%e A001678 : level sequence out-degrees (dots for zeros)
%e A001678 : 1: [ 0 1 2 3 3 2 1 ] [ 2 2 2 . . . . ]
%e A001678 : O--o--o--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 :
%e A001678 : 2: [ 0 1 2 2 2 2 1 ] [ 2 4 . . . . . ]
%e A001678 : O--o--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 :
%e A001678 : 3: [ 0 1 2 2 2 1 1 ] [ 3 3 . . . . . ]
%e A001678 : O--o--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 :
%e A001678 : 4: [ 0 1 2 2 1 2 2 ] [ 2 2 . . 2 . . ]
%e A001678 : O--o--o
%e A001678 : .--o
%e A001678 : .--o--o
%e A001678 : .--o
%e A001678 :
%e A001678 : 5: [ 0 1 2 2 1 1 1 ] [ 4 2 . . . . . ]
%e A001678 : O--o--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 :
%e A001678 : 6: [ 0 1 1 1 1 1 1 ] [ 6 . . . . . . ]
%e A001678 : O--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 : .--o
%e A001678 :
%e A001678 (End)
%e A001678 From _Gus Wiseman_, Jan 20 2020: (Start)
%e A001678 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 A001678 o . (oo) (ooo) (oooo) (ooooo) (oooooo) (ooooooo)
%e A001678 (o(oo)) (o(ooo)) (o(oooo)) (o(ooooo))
%e A001678 (oo(oo)) (oo(ooo)) (oo(oooo))
%e A001678 (ooo(oo)) (ooo(ooo))
%e A001678 ((oo)(oo)) (oooo(oo))
%e A001678 (o(o(oo))) ((oo)(ooo))
%e A001678 (o(o(ooo)))
%e A001678 (o(oo)(oo))
%e A001678 (o(oo(oo)))
%e A001678 (oo(o(oo)))
%e A001678 (End)
%p A001678 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 A001678 # second Maple program:
%p A001678 with(numtheory):
%p A001678 b:= proc(n) option remember; `if`(n=0, 1, add(add(
%p A001678 d*a(d+1), d=divisors(j))*b(n-j), j=1..n)/n)
%p A001678 end:
%p A001678 a:= proc(n) option remember; `if`(n<2, 0,
%p A001678 `if`(n=2, 1, b(n-2)-a(n-1)))
%p A001678 end:
%p A001678 seq(a(n), n=0..50); # _Alois P. Heinz_, Jul 02 2014
%t A001678 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 A001678 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 A001678 urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
%t A001678 Table[If[n<=1,0,Length[Select[urt[n-1],FreeQ[#,{_}]&]]],{n,0,10}] (* _Gus Wiseman_, Jan 20 2020 *)
%o A001678 (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 A001678 (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 A001678 Cf. A000014, A007827, A246403, A005202.
%Y A001678 Unlabeled rooted trees are counted by A000081.
%Y A001678 Topologically series-reduced rooted trees are counted by A001679.
%Y A001678 Labeled lone-child-avoiding rooted trees are counted by A060356.
%Y A001678 Labeled lone-child-avoiding unrooted trees are counted by A108919.
%Y A001678 Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
%Y A001678 Singleton-reduced rooted trees are counted by A330951.
%Y A001678 Cf. A000669, A004111, A106179, A198518, A254382, A331488, A331578.
%K A001678 nonn,easy,nice
%O A001678 0,7
%A A001678 _N. J. A. Sloane_
%E A001678 Additional comments from _Michael Somos_, Jun 05 2002