A001678 -id:A001678 - cp's OEIS frontend

A000014 Number of series-reduced trees with n nodes.

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

A318185 Number of totally transitive rooted trees with n nodes.

Original entry on oeis.org

1, 1, 1, 2, 3, 5, 7, 12, 17, 28, 41, 65, 96, 150, 221, 342, 506, 771, 1142, 1731, 2561, 3855, 5702, 8538, 12620, 18817, 27774, 41276, 60850, 90139

Offset: 1

Gus Wiseman, Aug 20 2018

A rooted tree is totally transitive if every branch of the root is totally transitive and every branch of a branch of the root is also a branch of the root. Unlike transitive rooted trees (A290689), every terminal subtree of a totally transitive rooted tree is itself totally transitive.

			The a(8) = 12 totally transitive rooted trees:
  (o(o)(o(o)))
  (o(o)(o)(o))
  (o(o)(ooo))
  (o(oo)(oo))
  (oo(o)(oo))
  (ooo(o)(o))
  (o(ooooo))
  (oo(oooo))
  (ooo(ooo))
  (oooo(oo))
  (ooooo(o))
  (ooooooo)
The a(9) = 17 totally transitive rooted trees:
  (o(o)(oo(o)))
  (oo(o)(o(o)))
  (o(o)(o)(oo))
  (oo(o)(o)(o))
  (o(o)(oooo))
  (o(oo)(ooo))
  (oo(o)(ooo))
  (oo(oo)(oo))
  (ooo(o)(oo))
  (oooo(o)(o))
  (o(oooooo))
  (oo(ooooo))
  (ooo(oooo))
  (oooo(ooo))
  (ooooo(oo))
  (oooooo(o))
  (oooooooo)

Cf. A000081, A001678, A004111, A279861, A290689, A290760, A290822, A318186, A318187.

totra[n_]:=totra[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[totra/@c]],Complement[Union@@#,#]=={}&],{c,IntegerPartitions[n-1]}]];
Table[Length[totra[n]],{n,20}]

A063895 Start with x, xy; then concatenate each word in turn with all preceding words, getting x xy xxy xxxy xyxxy xxxxy xyxxxy xxyxxxy ...; sequence gives number of words of length n. Also binary trees by degree: x (x,y) (x,(x,y)) (x,(x,(x,y))) ((x,y),(x,(x,y)))...

Original entry on oeis.org

1, 1, 1, 1, 2, 3, 6, 11, 22, 43, 88, 179, 372, 774, 1631, 3448, 7347, 15713, 33791, 72923, 158021, 343495, 749102, 1638103, 3591724, 7893802, 17387931, 38379200, 84875596, 188036830, 417284181, 927469845, 2064465341, 4601670625, 10270463565, 22950838755

Offset: 1

Claude Lenormand (claude.lenormand(AT)free.fr), Aug 29 2001

Also binary rooted identity trees (those with no symmetries, cf. A004111).
From Gus Wiseman, May 04 2021: (Start)
Also the number of unlabeled binary rooted semi-identity trees with 2*n - 1 nodes. In a semi-identity tree, only the non-leaf branches directly under any given vertex are required to be distinct. Alternatively, an unlabeled rooted tree is a semi-identity tree iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees. For example, the a(3) = 1 through a(6) = 6 trees are:
  (o(oo))  (o(o(oo)))  ((oo)(o(oo)))  ((oo)(o(o(oo))))  ((o(oo))(o(o(oo))))
                       (o(o(o(oo))))  (o((oo)(o(oo))))  ((oo)((oo)(o(oo))))
                                      (o(o(o(o(oo)))))  ((oo)(o(o(o(oo)))))
                                                        (o((oo)(o(o(oo)))))
                                                        (o(o((oo)(o(oo)))))
                                                        (o(o(o(o(o(oo))))))
The a(8) = 11 trees with 15 nodes:
  ((o(oo))((oo)(o(oo))))
  ((o(oo))(o(o(o(oo)))))
  ((oo)((oo)(o(o(oo)))))
  ((oo)(o((oo)(o(oo)))))
  ((oo)(o(o(o(o(oo))))))
  (o((o(oo))(o(o(oo)))))
  (o((oo)((oo)(o(oo)))))
  (o((oo)(o(o(o(oo))))))
  (o(o((oo)(o(o(oo))))))
  (o(o(o((oo)(o(oo))))))
  (o(o(o(o(o(o(oo)))))))
(End)

Alois P. Heinz, Table of n, a(n) for n = 1..1000
Index entries for sequences related to rooted trees

Cf. A063894, A036774.
The non-semi-identity version is 2*A001190(n)-1, ranked by A111299.
Semi-binary trees are also counted by A001190, but ranked by A292050.
The not necessarily binary version is A306200, ranked A306202.
The Matula-Goebel numbers of these trees are A339193.
The plane tree version is A343663.
A000081 counts unlabeled rooted trees with n nodes.
A004111 counts identity trees, ranked by A276625.
A306201 counts balanced semi-identity trees, ranked by A306203.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
Cf. A001678, A331934, A331963, A331964.

a:= proc(n) option remember; `if`(n<3, n*(3-n)/2, add(a(i)*a(n-i),
      i=1..(n-1)/2)+`if`(irem(n, 2, 'r')=0, (p->(p-1)*p/2)(a(r)), 0))
    end:
seq(a(n), n=1..50);  # Alois P. Heinz, Aug 02 2013

a[n_] := a[n] = If[n<3, n*(3-n)/2, Sum[a[i]*a[n-i], {i, 1, (n-1)/2}]+If[{q, r} = QuotientRemainder[n, 2]; r == 0, (a[q]-1)*a[q]/2, 0]]; Table[a[n], {n, 1, 36}] (* Jean-François Alcover, Feb 25 2014, after Alois P. Heinz *)
ursiq[n_]:=Join@@Table[Select[Union[Sort/@Tuples[ursiq/@ptn]],#=={}||#=={{},{}}||Length[#]==2&&(UnsameQ@@DeleteCases[#,{}])&],{ptn,IntegerPartitions[n-1]}];Table[Length[ursiq[n]],{n,1,15,2}] (* Gus Wiseman, May 04 2021 *)

{a(n)=local(A, m); if(n<1, 0, m=1; A=O(x); while( m<=n, m*=2; A=1-sqrt(1-2*x-2*x^2+subst(A, x, x^2))); polcoeff(A, n))}

a(n) = (sum a(i)*a(j), i+j=n, i2. a(1)=a(2)=1.
G.f. A(x) = 1-sqrt(1-2x-2x^2+A(x^2)) satisfies x+x^2-A(x)+(A(x)^2-A(x^2))/2=0, A(0)=0. - Michael Somos, Sep 06 2003
a(n) ~ c * d^n / n^(3/2), where d = 2.33141659246516873904600076533362924695..., c = 0.2873051160895040470174351963... . - Vaclav Kotesovec, Sep 11 2014

Additional comments and g.f. from Christian G. Bower, Nov 29 2001

A320160 Number of series-reduced balanced rooted trees whose leaves form an integer partition of n.

Original entry on oeis.org

1, 2, 3, 6, 9, 19, 31, 63, 110, 215, 391, 773, 1451, 2879, 5594, 11173, 22041, 44136, 87631, 175155, 348186, 694013, 1378911, 2743955, 5452833, 10853541, 21610732, 43122952, 86192274, 172753293, 347114772, 699602332, 1414033078, 2866580670, 5826842877, 11874508385

Offset: 1

Gus Wiseman, Oct 06 2018

nonn

A rooted tree is series-reduced if every non-leaf node has at least two branches, and balanced if all leaves are the same distance from the root.

Also the number of balanced unlabeled phylogenetic rooted trees with n leaves.

			The a(1) = 1 through a(6) = 19 rooted trees:
  1  2     3      4           5            6
     (11)  (12)   (13)        (14)         (15)
           (111)  (22)        (23)         (24)
                  (112)       (113)        (33)
                  (1111)      (122)        (114)
                  ((11)(11))  (1112)       (123)
                              (11111)      (222)
                              ((11)(12))   (1113)
                              ((11)(111))  (1122)
                                           (11112)
                                           (111111)
                                           ((11)(13))
                                           ((11)(22))
                                           ((12)(12))
                                           ((11)(112))
                                           ((12)(111))
                                           ((11)(1111))
                                           ((111)(111))
                                           ((11)(11)(11))

Andrew Howroyd, Table of n, a(n) for n = 1..500

Cf. A000081, A000311, A000669, A001678, A005804, A048816, A079500, A119262, A120803, A141268, A244925, A319312.

Cf. A316624, A320154, A320155, A320169, A320173, A320179.

sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
mps[set_]:=Union[Sort[Sort/@(#/.x_Integer:>set[[x]])]&/@sps[Range[Length[set]]]];
phy2[labs_]:=If[Length[labs]==1,labs,Union@@Table[Sort/@Tuples[phy2/@ptn],{ptn,Select[mps[Sort[labs]],Length[#1]>1&]}]];
Table[Sum[Length[Select[phy2[ptn],SameQ@@Length/@Position[#,_Integer]&]],{ptn,IntegerPartitions[n]}],{n,8}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(u=vector(n, n, 1), v=vector(n)); while(u, v+=u; u=EulerT(u)-u); v} \\ Andrew Howroyd, Oct 25 2018

Terms a(14) and beyond from Andrew Howroyd, Oct 25 2018

A331683 One and all numbers of the form 2^k * prime(j) for k > 0 and j already in the sequence.

Original entry on oeis.org

1, 4, 8, 14, 16, 28, 32, 38, 56, 64, 76, 86, 106, 112, 128, 152, 172, 212, 214, 224, 256, 262, 304, 326, 344, 424, 428, 448, 512, 524, 526, 608, 622, 652, 688, 766, 848, 856, 886, 896, 1024, 1048, 1052, 1154, 1216, 1226, 1244, 1304, 1376, 1438, 1532, 1696

Offset: 1

Gus Wiseman, Jan 30 2020

nonn

Also Matula-Goebel numbers of lone-child-avoiding rooted trees at with at most one non-leaf branch under any given vertex. A rooted tree is lone-child-avoiding if there are no unary branchings. The Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of the root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.

Also Matula-Goebel numbers of lone-child-avoiding locally disjoint semi-identity trees. Locally disjoint means no branch of any vertex overlaps a different (unequal) branch of the same vertex. In a semi-identity tree, all non-leaf branches of any given vertex are distinct.

			The sequence of all lone-child-avoiding rooted trees with at most one non-leaf branch under any given vertex together with their Matula-Goebel numbers begins:
    1: o
    4: (oo)
    8: (ooo)
   14: (o(oo))
   16: (oooo)
   28: (oo(oo))
   32: (ooooo)
   38: (o(ooo))
   56: (ooo(oo))
   64: (oooooo)
   76: (oo(ooo))
   86: (o(o(oo)))
  106: (o(oooo))
  112: (oooo(oo))
  128: (ooooooo)
  152: (ooo(ooo))
  172: (oo(o(oo)))
  212: (oo(oooo))
  214: (o(oo(oo)))
  224: (ooooo(oo))

Robert Israel, Table of n, a(n) for n = 1..3140

These trees counted by number of vertices are A212804.
The semi-lone-child-avoiding version is A331681.
The non-semi-identity version is A331871.
Lone-child-avoiding rooted trees are counted by A001678.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Unlabeled semi-identity trees are counted by A306200, with Matula-Goebel numbers A306202.
Locally disjoint rooted trees are counted by A316473.
Matula-Goebel numbers of locally disjoint rooted trees are A316495.
Lone-child-avoiding locally disjoint rooted trees by leaves are A316697.
Cf. A000081, A007097, A061775, A196050, A276625, A316470, A316696, A331678, A331679, A331680, A331682, A331686, A331687.

N:= 10^4: # for terms <= N
S:= {1}:
with(queue):
Q:= new(1):
while not empty(Q) do
  r:= dequeue(Q);
  p:= ithprime(r);
  newS:= {seq(2^i*p,i=1..ilog2(N/p))} minus S;
  S:= S union newS;
  for s in newS do enqueue(Q,s) od:
od:
sort(convert(S,list)); # Robert Israel, Feb 05 2020

uryQ[n_]:=n==1||MatchQ[FactorInteger[n],({{2,},{p,1}}/;uryQ[PrimePi[p]])|({{2,k_}}/;k>1)];
Select[Range[100],uryQ]

Intersection of A291636, A316495, and A306202.

A050381 Number of series-reduced planted trees with n leaves of 2 colors.

Original entry on oeis.org

2, 3, 10, 40, 170, 785, 3770, 18805, 96180, 502381, 2667034, 14351775, 78096654, 429025553, 2376075922, 13252492311, 74372374366, 419651663108, 2379399524742, 13549601275893, 77460249369658, 444389519874841

Offset: 1

Christian G. Bower, Nov 15 1999

nonn

Consider the free algebraic system with two commutative associative operators (x+y) and (x*y) and two generators A,B. The number of elements with n occurrences of the generators is 2*a(n) if n>1, and the number of generators if n=1. - Michael Somos, Aug 07 2017
From Gus Wiseman, Feb 07 2020: (Start)
Also the number of semi-lone-child-avoiding rooted trees with n leaves. Semi-lone-child-avoiding means there are no vertices with exactly one child unless that child is an endpoint/leaf. For example, the a(1) = 2 through a(3) = 10 trees are:
  o    (oo)      (ooo)
  (o)  (o(o))    (o(oo))
       ((o)(o))  (oo(o))
                 ((o)(oo))
                 (o(o)(o))
                 (o(o(o)))
                 ((o)(o)(o))
                 ((o)(o(o)))
                 (o((o)(o)))
                 ((o)((o)(o)))
(End)

			For n=2, the 2*a(2) = 6 elements are: A+A, A+B, B+B, A*A, A*B, B*B. - _Michael Somos_, Aug 07 2017

Andrew Howroyd, Table of n, a(n) for n = 1..500
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], (30-June-2014).
F. Chapoton, F. Hivert, J.-C. Novelli, A set-operad of formal fractions and dendriform-like sub-operads, arXiv preprint arXiv:1307.0092 [math.CO], 2013.
V. P. Johnson, Enumeration Results on Leaf Labeled Trees, Ph. D. Dissertation, Univ. Southern Calif., 2012. - From _N. J. A. Sloane_, Dec 22 2012
N. J. A. Sloane, Transforms
Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.
Index entries for sequences related to rooted trees

Column 2 of A319254.
Cf. A029856, A031148.
Lone-child-avoiding rooted trees with n leaves are A000669.
Lone-child-avoiding rooted trees with n vertices are A001678.
The locally disjoint case is A331874.
Semi-lone-child-avoiding rooted trees with n vertices are A331934.
Matula-Goebel numbers of these trees are A331935.
Cf. A000081, A005804, A141268, A196545, A291636, A316697, A330465, A331872, A331933, A331964.

terms = 22;
B[x_] = x O[x]^(terms+1);
A[x_] = 1/(1 - x + B[x])^2;
Do[A[x_] = A[x]/(1 - x^k + B[x])^Coefficient[A[x], x, k] + O[x]^(terms+1) // Normal, {k, 2, terms+1}];
Join[{2}, Drop[CoefficientList[A[x], x]/2, 2]] (* Jean-François Alcover, Aug 17 2018, after Michael Somos *)
slaurte[n_]:=If[n==1,{o,{o}},Join@@Table[Union[Sort/@Tuples[slaurte/@ptn]],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[slaurte[n]],{n,10}] (* Gus Wiseman, Feb 07 2020 *)

{a(n) = my(A, B); if( n<2, 2*(n>0), B = x * O(x^n); A = 1 / (1 - x + B)^2; for(k=2, n, A /= (1 - x^k + B)^polcoeff(A, k)); polcoeff(A, n)/2)}; /* Michael Somos, Aug 07 2017 */

Doubles (index 2+) under EULER transform.
Product_{k>=1} (1-x^k)^-a(k) = 1 + a(1)*x + Sum_{k>=2} 2*a(k)*x^k. - Michael Somos, Aug 07 2017
a(n) ~ c * d^n / n^(3/2), where d = 6.158893517087396289837838459951206775682824030495453326610366016992093939... and c = 0.1914250508201011360729769525164141605187995730026600722369002... - Vaclav Kotesovec, Aug 17 2018

A108919 Number of series-reduced labeled trees with n nodes.

Original entry on oeis.org

1, 0, 1, 1, 13, 51, 601, 4803, 63673, 775351, 12186061, 196158183, 3661759333, 72413918019, 1583407093633, 36916485570331, 929770285841137, 24904721121298671, 711342228666833173, 21502519995056598639, 687345492498807434461, 23135454269839313430715, 818568166383797223246601, 30357965273255025673685091

Offset: 1

Vladeta Jovovic, Jul 20 2005

"Series-reduced" means that if the tree is rooted at 1, then there is no node with just a single child.

Callan points out that A002792 is an incorrect version of this sequence. - Joerg Arndt, Jul 01 2014

Seiichi Manyama, Table of n, a(n) for n = 1..415
David Callan, A sign-reversing involution to count labeled lone-child-avoiding trees, arXiv:1406.7784 [math.CO], 2014.

The rooted version is A060356.

Cf. A000311, A000669, A001678, A292504, A316651, A316652, A318231, A318813, A330465, A330624, A352410.

f[n_] := Sum[(-1)^(n-k)*n!/k!*Binomial[n-1, k-1]*k^(k-1), {k, n}]/n; Table[ f[n], {n, 20}] (* Robert G. Wilson v, Jul 21 2005 *)

a(n) = { 1/n * sum(k=1, n, (-1)^(n-k) * binomial(n,k) * (n-1)!/(k-1)! * k^(k-1) ); } \\ Joerg Arndt, Aug 28 2014

a(n) = A060356(n)/n.
1 = Sum_{n>=0} a(n+1)*(exp(x)-x)^(-n-1)*x^n/n!.
E.g.f.: A(x) = Sum_{n>=0} a(n+1)*x^n/n! satisfies A(x) = exp(x*A(x))/(1+x). - Olivier Gérard, Dec 31 2013 (edited by Gus Wiseman, Dec 31 2019)
E.g.f.: -Integral (LambertW(-x/(1 + x))/x) dx. - Ilya Gutkovskiy, Jul 01 2020

More terms from Robert G. Wilson v, Jul 21 2005
New name (from A002792) by Joerg Arndt, Aug 28 2014
Offset corrected by Gus Wiseman, Dec 31 2019

A331934 Number of semi-lone-child-avoiding rooted trees with n unlabeled vertices.

Original entry on oeis.org

1, 1, 1, 2, 4, 7, 15, 29, 62, 129, 279, 602, 1326, 2928, 6544, 14692, 33233, 75512, 172506, 395633, 911108, 2105261, 4880535, 11346694, 26451357, 61813588, 144781303, 339820852, 799168292, 1882845298, 4443543279, 10503486112, 24864797324, 58944602767, 139918663784

Offset: 1

Gus Wiseman, Feb 03 2020

nonn

A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless the child is an endpoint/leaf.

			The a(1) = 1 through a(7) = 15 trees:
  o  (o)  (oo)  (ooo)   (oooo)    (ooooo)    (oooooo)
                (o(o))  (o(oo))   (o(ooo))   (o(oooo))
                        (oo(o))   (oo(oo))   (oo(ooo))
                        ((o)(o))  (ooo(o))   (ooo(oo))
                                  ((o)(oo))  (oooo(o))
                                  (o(o)(o))  ((o)(ooo))
                                  (o(o(o)))  ((oo)(oo))
                                             (o(o)(oo))
                                             (o(o(oo)))
                                             (o(oo(o)))
                                             (oo(o)(o))
                                             (oo(o(o)))
                                             ((o)(o)(o))
                                             ((o)(o(o)))
                                             (o((o)(o)))

Andrew Howroyd, Table of n, a(n) for n = 1..1000
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.

The same trees counted by leaves are A050381.
The locally disjoint version is A331872.
Matula-Goebel numbers of these trees are A331935.
Lone-child-avoiding rooted trees are A001678.
Cf. A000081, A000669, A198518, A289501, A291636, A306200, A320268, A330465, A330951, A331873, A331874, A331933, A331966.

sse[n_]:=Switch[n,1,{{}},2,{{{}}},_,Join@@Function[c,Union[Sort/@Tuples[sse/@c]]]/@Rest[IntegerPartitions[n-1]]];
Table[Length[sse[n]],{n,10}]

EulerT(v)={Vec(exp(x*Ser(dirmul(v,vector(#v,n,1/n))))-1, -#v)}
seq(n)={my(v=[1,1]); for(n=2, n-1, v=concat(v, EulerT(v)[n] - v[n])); v} \\ Andrew Howroyd, Feb 09 2020

Product_{k > 0} 1/(1 - x^k)^a(k) = A(x) + A(x)/x - x where A(x) = Sum_{k > 0} x^k a(k).

Euler transform is b(1) = 1, b(n > 1) = a(n) + a(n + 1).

Terms a(25) and beyond from Andrew Howroyd, Feb 09 2020

A298426 Regular triangle where T(n,k) is number of k-ary rooted trees with n nodes.

Original entry on oeis.org

1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 1, 1, 0, 1, 0, 1, 0, 0, 0, 1, 0, 1, 2, 1, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 3, 0, 1, 0, 0, 0, 1, 0, 1, 0, 2, 0, 0, 0, 0, 0, 1, 0, 1, 6, 0, 0, 1, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 11, 4, 2, 0, 1, 0, 0, 0, 0, 0, 1, 0, 1, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 0, 1, 0, 1, 23, 0, 0, 0, 0, 1, 0, 0, 0, 0, 0, 0, 1

Offset: 1

Gus Wiseman, Jan 19 2018

Row sums are A298422.

			Triangle begins:
1
0  1
0  1  1
0  1  0  1
0  1  1  0  1
0  1  0  0  0  1
0  1  2  1  0  0  1
0  1  0  0  0  0  0  1
0  1  3  0  1  0  0  0  1
0  1  0  2  0  0  0  0  0  1
0  1  6  0  0  1  0  0  0  0  1
0  1  0  0  0  0  0  0  0  0  0  1
0  1  11 4  2  0  1  0  0  0  0  0  1
0  1  0  0  0  0  0  0  0  0  0  0  0  1
0  1  23 0  0  0  0  1  0  0  0  0  0  0  1
0  1  0  8  0  2  0  0  0  0  0  0  0  0  0  1

Alois P. Heinz, Rows n = 1..200, flattened

Cf. A000005, A000081, A000598, A001190, A001678, A003238, A004111, A067538, A143773, A289078, A289079, A295461, A298118, A298422, A298423, A298424.

nn=16;
arut[n_,k_]:=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[arut[#,k]&/@c]]]/@Select[IntegerPartitions[n-1],Length[#]===k&]]
Table[arut[n,k]//Length,{n,nn},{k,0,n-1}]

A358372 Number of nodes in the n-th standard ordered rooted tree.

Original entry on oeis.org

1, 2, 3, 3, 4, 4, 4, 4, 4, 5, 5, 5, 5, 5, 5, 5, 5, 5, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 6, 6, 6, 6, 5, 6, 6, 6, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 6, 6, 7, 7, 7, 7, 7, 7, 6, 7, 7, 7, 7, 7, 7, 7, 5, 6, 7, 7, 7, 7, 7, 7, 7, 8, 8, 8, 8, 8, 8, 8, 7, 7, 8, 8, 8, 8, 8

Offset: 1

Gus Wiseman, Nov 14 2022

nonn

We define the n-th standard ordered rooted tree to be obtained by taking the (n-1)-th composition in standard order (graded reverse-lexicographic, A066099) as root and replacing each part with its own standard ordered rooted tree. This ranking is an ordered variation of Matula-Goebel numbers, giving a bijective correspondence between positive integers and unlabeled ordered rooted trees.

			The standard ordered rooted tree ranking begins:
  1: o        10: (((o))o)   19: (((o))(o))
  2: (o)      11: ((o)(o))   20: (((o))oo)
  3: ((o))    12: ((o)oo)    21: ((o)((o)))
  4: (oo)     13: (o((o)))   22: ((o)(o)o)
  5: (((o)))  14: (o(o)o)    23: ((o)o(o))
  6: ((o)o)   15: (oo(o))    24: ((o)ooo)
  7: (o(o))   16: (oooo)     25: (o(oo))
  8: (ooo)    17: ((((o))))  26: (o((o))o)
  9: ((oo))   18: ((oo)o)    27: (o(o)(o))
For example, the 25th ordered tree is (o,(o,o)) because the 24th composition is (1,4) and the 3rd composition is (1,1). Hence a(25) = 5.

Gus Wiseman, Statistics, classes, and transformations of standard compositions

The triangle counting trees by leaves is A001263, unordered A055277.
The version for unordered trees is A061775, leaves A109129, edges A196050.
The leaves are counted by A358371.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358374 ranks ordered identity trees, counted by A032027.
A358375 ranks ordered binary trees, counted by A126120
Cf. A001678, A004249, A005043, A063895, A284778, A358373, A358376, A358377.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Table[Count[srt[n],_,{0,Infinity}],{n,100}]

cp's OEIS Frontend

A000014 Number of series-reduced trees with n nodes.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A318185 Number of totally transitive rooted trees with n nodes.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A063895 Start with x, xy; then concatenate each word in turn with all preceding words, getting x xy xxy xxxy xyxxy xxxxy xyxxxy xxyxxxy ...; sequence gives number of words of length n. Also binary trees by degree: x (x,y) (x,(x,y)) (x,(x,(x,y))) ((x,y),(x,(x,y)))...

Views

Author

Keywords

Comments

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

Extensions

A320160 Number of series-reduced balanced rooted trees whose leaves form an integer partition of n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A331683 One and all numbers of the form 2^k * prime(j) for k > 0 and j already in the sequence.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A050381 Number of series-reduced planted trees with n leaves of 2 colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A108919 Number of series-reduced labeled trees with n nodes.

Views

Author

Keywords

Comments

Links

Crossrefs