A246403 -id:A246403 - cp's OEIS frontend

A001678 Number of series-reduced planted trees with n nodes.

0, 0, 1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127, 248, 482, 952, 1885, 3765, 7546, 15221, 30802, 62620, 127702, 261335, 536278, 1103600, 2276499, 4706985, 9752585, 20247033, 42110393, 87733197, 183074638, 382599946, 800701320, 1677922740, 3520581954

Offset: 0

N. J. A. Sloane

The initial term is 0 by convention, though a good case can be made that it should be 1 instead.
Series-reduced trees contain no node with valency 2; see A000014 for the unrooted series-reduced trees. - Joerg Arndt, Mar 03 2015
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
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
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

			--------------- Examples (i=internal,e=external): ---------------------------
|.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...i...|.e.e.e.e.e...e....i....e.e...i...|
|..e..|...i...|...i...|....i........i.....|.....i..........i..........i.....|
|..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 + ...
From _Joerg Arndt_, Jun 28 2014: (Start)
The a(8) = 6 rooted trees with 7 nodes as described in the comment are:
:           level sequence       out-degrees (dots for zeros)
:     1:  [ 0 1 2 3 3 2 1 ]    [ 2 2 2 . . . . ]
:  O--o--o--o
:        .--o
:     .--o
:  .--o
:
:     2:  [ 0 1 2 2 2 2 1 ]    [ 2 4 . . . . . ]
:  O--o--o
:     .--o
:     .--o
:     .--o
:  .--o
:
:     3:  [ 0 1 2 2 2 1 1 ]    [ 3 3 . . . . . ]
:  O--o--o
:     .--o
:     .--o
:  .--o
:  .--o
:
:     4:  [ 0 1 2 2 1 2 2 ]    [ 2 2 . . 2 . . ]
:  O--o--o
:     .--o
:  .--o--o
:     .--o
:
:     5:  [ 0 1 2 2 1 1 1 ]    [ 4 2 . . . . . ]
:  O--o--o
:     .--o
:  .--o
:  .--o
:  .--o
:
:     6:  [ 0 1 1 1 1 1 1 ]    [ 6 . . . . . . ]
:  O--o
:  .--o
:  .--o
:  .--o
:  .--o
:  .--o
:
(End)
From _Gus Wiseman_, Jan 20 2020: (Start)
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:
  o   .   (oo)  (ooo)  (oooo)   (ooooo)   (oooooo)    (ooooooo)
                       (o(oo))  (o(ooo))  (o(oooo))   (o(ooooo))
                                (oo(oo))  (oo(ooo))   (oo(oooo))
                                          (ooo(oo))   (ooo(ooo))
                                          ((oo)(oo))  (oooo(oo))
                                          (o(o(oo)))  ((oo)(ooo))
                                                      (o(o(ooo)))
                                                      (o(oo)(oo))
                                                      (o(oo(oo)))
                                                      (oo(o(oo)))
(End)

D. G. Cantor, personal communication.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 525.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62.
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).

Alois P. Heinz, Table of n, a(n) for n = 0..1000 (first 501 terms from Christian G. Bower)
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
F. Harary and E. M. Palmer, Probability that a point of a tree is fixed, Math. Proc. Camb. Phil. Soc. 85 (1979) 407-415.
F. Harary and G. Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
INRIA Algorithms Project, Encyclopedia of Combinatorial Structures 404
Marko Riedel, 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.
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

Cf. A000014, A007827, A246403, A005202.
Unlabeled rooted trees are counted by A000081.
Topologically series-reduced rooted trees are counted by A001679.
Labeled lone-child-avoiding rooted trees are counted by A060356.
Labeled lone-child-avoiding unrooted trees are counted by A108919.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Singleton-reduced rooted trees are counted by A330951.
Cf. A000669, A004111, A106179, A198518, A254382, A331488, A331578.

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)
# second Maple program:
with(numtheory):
b:= proc(n) option remember; `if`(n=0, 1, add(add(
       d*a(d+1), d=divisors(j))*b(n-j), j=1..n)/n)
    end:
a:= proc(n) option remember; `if`(n<2, 0,
      `if`(n=2, 1, b(n-2)-a(n-1)))
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 02 2014

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 *)
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 *)
urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[If[n<=1,0,Length[Select[urt[n-1],FreeQ[#,{}]&]]],{n,0,10}] (* _Gus Wiseman, Jan 20 2020 *)

(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 */

{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 */

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)].
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
a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.189461985660850563... and c = 0.1924225474701550354144525345664845514828912790855223729854471406053655209... - Vaclav Kotesovec, Jun 26 2014
a(n) = Sum_{i=2..n-2} A106179(i, n-1-i) for n >= 3. - Andrew Howroyd, Mar 29 2021

Additional comments from Michael Somos, Jun 05 2002

A000014 Number of series-reduced trees with n nodes.

Original entry on oeis.org

0, 1, 1, 0, 1, 1, 2, 2, 4, 5, 10, 14, 26, 42, 78, 132, 249, 445, 842, 1561, 2988, 5671, 10981, 21209, 41472, 81181, 160176, 316749, 629933, 1256070, 2515169, 5049816, 10172638, 20543579, 41602425, 84440886, 171794492, 350238175, 715497037, 1464407113

Offset: 0

N. J. A. Sloane

Other terms for "series-reduced tree": (i) homeomorphically irreducible tree, (ii) homeomorphically reduced tree, (iii) reduced tree, (iv) topological tree.

In a series-reduced tree, vertices cannot have degree 2; they can be leaves or have >= 2 branches.

			G.f. = x + x^2 + x^4 + x^5 + 2*x^6 + 2*x^7 + 4*x^8 + 5*x^9 + 10*x^10 + ...
The star graph with n nodes (except for n=3) is a series-reduced tree. For n=6 the other series-reduced tree is shaped like the letter H. - _Michael Somos_, Dec 19 2014

F. Bergeron, G. Labelle and P. Leroux, Combinatorial Species and Tree-Like Structures, Camb. 1998, p. 284.
D. G. Cantor, personal communication.
F. Harary, Graph Theory. Addison-Wesley, Reading, MA, 1969, p. 232.
F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Fig. 3.3.3.
J. L. Gross and J. Yellen, eds., Handbook of Graph Theory, CRC Press, 2004; p. 526.
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).

Matthew Parker, Table of n, a(n) for n = 0..1000 (first 501 terms from Christian G. Bower)
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], 30 June 2014.
Ira M. Gessel, Good Will Hunting's Problem: Counting Homeomorphically Irreducible Trees, arXiv:2305.03157 [math.CO], 2023.
James Grime and Brady Haran, The problem in Good Will Hunting, 2013 (Numberphile video).
Frank Harary and Geert Prins, The number of homeomorphically irreducible trees and other species, Acta Math., 101 (1959), 141-162.
F. Harary, R. W. Robinson and A. J. Schwenk, Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A, 20 (1975), 483-503.
F. Harary, R. W. Robinson and A. J. Schwenk, Corrigenda: Twenty-step algorithm for determining the asymptotic number of trees of various species, J. Austral. Math. Soc., Series A 41 (1986), p. 325.
P. Leroux and B. Miloudi, Généralisations de la formule d'Otter, Ann. Sci. Math. Québec, Vol. 16, No. 1, pp. 53-80, 1992. (Annotated scanned copy)
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes.
B. D. McKay, Lists of Trees sorted by diameter and Homeomorphically irreducible trees, with <= 22 nodes. [Cached copy of top page only, pdf file, no active links, with permission]
Matthew Parker, The first 2000 terms (7-Zip compressed file)
A. J. Schwenk, Letter to N. J. A. Sloane, Aug 1972
N. J. A. Sloane, Illustration of initial terms
Peter Steinbach, Field Guide to Simple Graphs, Volume 1, Part 17 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Peter Steinbach, Field Guide to Simple Graphs, Volume 3, Part 12 (For Volumes 1, 2, 3, 4 of this book see A000088, A008406, A000055, A000664, respectively.)
Eric Weisstein's World of Mathematics, Series-Reduced Tree
Index entries for sequences related to trees
Index entries for "core" sequences

Cf. A000055 (trees), A001678 (series-reduced planted trees), A007827 (series-reduced trees by leaves), A271205 (series-reduced trees by leaves and nodes).

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:
G059123 := G0temp / x + G0temp - (G0temp^2+eval(G0temp,x=x^2))/(2*x):
G000014 := ((x-1)/x) * G059123 + ((1+x)/x^2) * G0temp - (1/x^2) * G0temp^2:
A000014 := 0,seq(coeff(G000014,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)

a[n_] := If[n<1, 0, A = x/(1-x^2) + x*O[x]^n; For[k=3, k <= n-1, k++, A = A/(1 - x^k + x*O[x]^n)^SeriesCoefficient[A, k]]; s = ((Normal[A] /. x -> x^2) + O[x]^(2n))*(1-x) + A*(2-A)*(1+x); SeriesCoefficient[s, n]/2]; Table[a[n], {n, 0, 40}] (* Jean-François Alcover, Feb 02 2016, adapted from PARI *)

{a(n) = my(A); if( n<1, 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( (subst(A, x, x^2) * (1 - x) + A * (2 - A) * (1 + x)) / 2, n))}; /* Michael Somos, Dec 19 2014 */

G.f.: A(x) = ((x-1)/x)*f(x) + ((1+x)/x^2)*g(x) - (1/x^2)*g(x)^2 where f(x) is g.f. for A059123 and g(x) is g.f. for A001678. [Harary and E. M. Palmer, p. 62, Eq. (3.3.10) with extra -(1/x^2)*Hbar(x)^2 term which should be there according to eq.(3.3.14), p. 63, with eq.(3.3.9)]. [corrected by Wolfdieter Lang, Jan 09 2001]

a(n) ~ c * d^n / n^(5/2), where d = A246403 = 2.189461985660850..., c = 0.684447272004914061023163279794145361469033868145768075109924585532604582794... - Vaclav Kotesovec, Aug 25 2014

A001679 Number of series-reduced rooted trees with n nodes.

Original entry on oeis.org

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

N. J. A. Sloane

nonn

Also known as homeomorphically irreducible rooted trees, or rooted trees without nodes of degree 2.

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

			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)

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).

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

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.
The labeled version is A060313, with unrooted case A005512.
Matula-Goebel numbers of these trees are given by A331489.
Lone-child-avoiding rooted trees are counted by A001678(n + 1).
Cf. A004111, A060356, A198518, A254382, A291636, A330951, A331488, A331578.

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

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 *)

{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))};

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

Additional comments from Michael Somos, Oct 10 2003

A198518 G.f. satisfies: A(x) = exp( Sum_{n>=1} A(x^n)/(1+x^n) * x^n/n ).

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 9, 16, 29, 54, 102, 194, 375, 730, 1434, 2837, 5650, 11311, 22767, 46023, 93422, 190322, 389037, 797613, 1639878, 3380099, 6983484, 14459570, 29999618, 62357426, 129843590, 270807835, 565674584, 1183301266, 2478624060, 5198504694, 10916110768, 22948299899

Offset: 0

Paul D. Hanna, Oct 26 2011

nonn

For n>=1, a(n) is the number of rooted trees (see A000081) with n non-root nodes where non-root nodes cannot have out-degree 1, see the note by David Callan and the example. Imposing the condition also for the root node gives A001678. - Joerg Arndt, Jun 28 2014
Compare definition to G(x) = exp( Sum_{n>=1} G(x^n)*x^n/n ), where G(x) is the g.f. of A000081, the number of rooted trees with n nodes.
Number of forests of lone-child-avoiding rooted trees with n unlabeled vertices. - Gus Wiseman, Feb 03 2020

			G.f.: A(x) = 1 + x + x^2 + 2*x^3 + 3*x^4 + 5*x^5 + 9*x^6 + 16*x^7 + 29*x^8 +...
where
log(A(x)) = A(x)/(1+x)*x + A(x^2)/(1+x^2)*x^2/2 + A(x^3)/(1+x^3)*x^3/3 +...
The coefficients in A(x)/(1+x) begin:
[1, 0, 1, 1, 2, 3, 6, 10, 19, 35, 67, 127, 248, 482, 952, 1885, 3765, ...]
(this is, up to offset, A001678),
from which g.f. A(x) may be generated by the Euler transform:
A(x) = 1/((1-x)^1*(1-x^2)^0*(1-x^3)^1*(1-x^4)^1*(1-x^5)^2*(1-x^6)^3*(1-x^7)^6*(1-x^8)^10*(1-x^9)^19*(1-x^10)^35*...).
From _Joerg Arndt_, Jun 28 2014: (Start)
The a(6) = 9 rooted trees with 6 non-root nodes as described in the comment are:
:           level sequence       out-degrees (dots for zeros)
:     1:  [ 0 1 2 3 3 3 2 ]    [ 1 2 3 . . . . ]
:  O--o--o--o
:        .--o
:        .--o
:     .--o
:
:     2:  [ 0 1 2 3 3 2 2 ]    [ 1 3 2 . . . . ]
:  O--o--o--o
:        .--o
:     .--o
:     .--o
:
:     3:  [ 0 1 2 3 3 2 1 ]    [ 2 2 2 . . . . ]
:  O--o--o--o
:        .--o
:     .--o
:  .--o
:
:     4:  [ 0 1 2 2 2 2 2 ]    [ 1 5 . . . . . ]
:  O--o--o
:     .--o
:     .--o
:     .--o
:     .--o
:
:     5:  [ 0 1 2 2 2 2 1 ]    [ 2 4 . . . . . ]
:  O--o--o
:     .--o
:     .--o
:     .--o
:  .--o
:
:     6:  [ 0 1 2 2 2 1 1 ]    [ 3 3 . . . . . ]
:  O--o--o
:     .--o
:     .--o
:  .--o
:  .--o
:
:     7:  [ 0 1 2 2 1 2 2 ]    [ 2 2 . . 2 . . ]
:  O--o--o
:     .--o
:  .--o--o
:     .--o
:
:     8:  [ 0 1 2 2 1 1 1 ]    [ 4 2 . . . . . ]
:  O--o--o
:     .--o
:  .--o
:  .--o
:  .--o
:
:     9:  [ 0 1 1 1 1 1 1 ]    [ 6 . . . . . . ]
:  O--o
:  .--o
:  .--o
:  .--o
:  .--o
:  .--o
(End)
From _Gus Wiseman_, Jan 22 2020: (Start)
The a(0) = 1 through a(6) = 9 rooted trees with n + 1 nodes where non-root vertices cannot have out-degree 1:
  o  (o)  (oo)  (ooo)   (oooo)   (ooooo)    (oooooo)
                ((oo))  ((ooo))  ((oooo))   ((ooooo))
                        (o(oo))  (o(ooo))   (o(oooo))
                                 (oo(oo))   (oo(ooo))
                                 ((o(oo)))  (ooo(oo))
                                            ((o(ooo)))
                                            ((oo)(oo))
                                            ((oo(oo)))
                                            (o(o(oo)))
(End)

Alois P. Heinz, Table of n, a(n) for n = 0..1000
David Callan, Rooted trees with no out-degree = 1, (7-July-2014).
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A052855, A246403.
The labeled version is A254382.
Unlabeled rooted trees are A000081.
Lone-child-avoiding rooted trees are A001678(n+1).
Topologically series-reduced rooted trees are A001679.
Labeled lone-child-avoiding rooted trees are A060356.
Cf. A000669, A004111, A108919, A291636, A330951, A331488, A331934.

with(numtheory):
b:= proc(n) b(n):= `if`(n=0, 1, a(n)-b(n-1)) end:
a:= proc(n) option remember; `if`(n=0, 1, add(add(
       d*b(d-1), d=divisors(j))*a(n-j), j=1..n)/n)
    end:
seq(a(n), n=0..50);  # Alois P. Heinz, Jul 02 2014

b[n_] := b[n] = If[n==0, 1, a[n] - b[n-1]];
a[n_] := a[n] = If[n==0, 1, Sum[Sum[d*b[d-1], {d, Divisors[j]}]*a[n-j], {j, 1, n}]/n];
Table[a[n], {n, 0, 50}] (* Jean-François Alcover, Mar 21 2017, after Alois P. Heinz *)
urt[n_]:=Join@@Table[Union[Sort/@Tuples[urt/@ptn]],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[urt[n],FreeQ[Z@@#,{}]&]],{n,10}] (* _Gus Wiseman, Jan 22 2020 *)

{a(n)=local(A=1+x);for(i=1,n,A=exp(sum(m=1,n,subst(A/(1+x),x,x^m+x*O(x^n))*x^m/m)));polcoeff(A,n)}

Euler transform of coefficients in A(x)/(1+x), where g.f. A(x) = Sum_{n>=0} a(n)*x^n.
a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711..., c = 1.3437262442171062526771597... . - Vaclav Kotesovec, Sep 03 2014
a(n) = A001678(n + 1) + A001678(n + 2). - Gus Wiseman, Jan 22 2020
Euler transform of A001678(n + 1). - Gus Wiseman, Feb 03 2020

A059123 Number of homeomorphically irreducible rooted trees (also known as series-reduced rooted trees, or rooted trees without nodes of degree 2) with n >= 1 nodes.

Original entry on oeis.org

0, 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

Offset: 0

Wolfdieter Lang, Jan 09 2001

Essentially the same as A001679. - Eric W. Weisstein, Mar 25 2022

			G.f. = x + x^2 + 2*x^4 + 2*x^5 + 4*x^6 + 6*x^7 + 12*x^8 + 20*x^9 + ...

F. Harary and E. M. Palmer, Graphical Enumeration, Academic Press, NY, 1973, p. 62, Eq. (3.3.9).

N. J. A. Sloane, Alois P. Heinz and Vaclav Kotesovec, Table of n, a(n) for n = 0..1000
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014)
P. J. Cameron, Some treelike objects, Quart. J. Math. Oxford, 38 (1987), 155-183.
N. J. A. Sloane, Illustration of initial terms
Index entries for sequences related to trees
Index entries for sequences related to rooted trees

Cf. A001679.
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.

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:
G059123 := G0temp / x + G0temp - (G0temp^2+eval(G0temp,x=x^2))/(2*x): A059123 := 0,seq(coeff(G059123,x^i),i=1..n); # Ulrich Schimke (ulrschimke(AT)aol.com)

terms = 36; (* 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] - 1, x] (* Jean-François Alcover, May 25 2012, updated Jan 12 2018 *)

{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))}; /* Michael Somos, Jun 13 2014 */

G.f.: 1 + ((1+x)/x)*f(x) - (f(x)^2+f(x^2))/(2*x) where 1+f(x) is g.f. for A001678 (homeomorphically irreducible planted trees by nodes).
a(n) = A001679(n) if n>0. - Michael Somos, Jun 13 2014
a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711... and c = 0.421301852869924921096502830935802411658488216342994235732491571594804013... - Vaclav Kotesovec, Jun 26 2014

A244456 Number of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals 2.

Original entry on oeis.org

1, 0, 1, 2, 4, 7, 15, 28, 56, 110, 220, 436, 878, 1762, 3560, 7205, 14650, 29838, 60991, 124938, 256628, 528238, 1089834, 2252860, 4666304, 9682422, 20125777, 41900433, 87369029, 182441944, 381499040, 798782945, 1674575394, 3514733683, 7385298837, 15534856067

Offset: 3

Joerg Arndt and Alois P. Heinz, Jun 29 2014

nonn

			a(5) = 1:
      o
     / \
    o   o
   / \
  o   o

Alois P. Heinz, Table of n, a(n) for n = 3..900

Column k=2 of A244454.

Cf. A244531, A246403.

b:= proc(n, i, t, k) option remember; `if`(n=0, `if`(t in [0, k],
      1, 0), `if`(i<1 or t>n, 0, add(binomial(b((i-1)$2, k$2)+j-1, j)*
      b(n-i*j, i-1, max(0,t-j), k), j=0..n/i)))
    end:
a:= n-> b(n-1$2, 2$2) -b(n-1$2, 3$2):
seq(a(n), n=3..40);

b[n_, i_, t_, k_] := b[n, i, t, k] = If[n == 0, If[t == 0 || t == k, 1, 0], If[i < 1, 0, Sum[Binomial[b[i - 1, i - 1, k, k] + j - 1, j]*b[n - i*j, i - 1, Max[0, t - j], k], {j, 0, n/i}]]]; a[n_] := b[n - 1, n - 1, 2, 2] - b[n - 1, n - 1, 3, 3] // FullSimplify; Table[a[n], {n, 3, 40}] (* Jean-François Alcover, Feb 06 2015, after Maple *)

a(n) ~ c * d^n / n^(3/2), where d = A246403 = 2.18946198566085056388702757711..., c = 0.4213018528699249210965028... (constants are same as for A001679). - Vaclav Kotesovec, Jul 02 2014

cp's OEIS Frontend

A001678 Number of series-reduced planted trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

PARI

Formula

Extensions

A000014 Number of series-reduced trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A001679 Number of series-reduced rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A198518 G.f. satisfies: A(x) = exp( Sum_{n>=1} A(x^n)/(1+x^n) * x^n/n ).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A059123 Number of homeomorphically irreducible rooted trees (also known as series-reduced rooted trees, or rooted trees without nodes of degree 2) with n >= 1 nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A244456 Number of unlabeled rooted trees with n nodes such that the minimal outdegree of inner nodes equals 2.

Views

Author

Keywords

Examples

Links

Crossrefs