A291636 -id:A291636 - 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

A339645 Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.

Original entry on oeis.org

1, 1, 1, 2, 3, 2, 5, 17, 12, 5, 12, 73, 95, 44, 12, 33, 369, 721, 512, 168, 33, 90, 1795, 5487, 5480, 2556, 625, 90, 261, 9192, 41945, 58990, 36711, 12306, 2342, 261, 766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766, 2312, 249164, 2483192, 6593103, 7141755, 3965673, 1283624, 258887, 32313, 2312

Offset: 1

Andrew Howroyd, Dec 11 2020

Only the leaves are colored. Equivalence is up to permutation of the colors.

Lone-child-avoiding rooted trees are also called planted series-reduced trees in some other sequences.

			Triangle begins:
    1;
    1,     1;
    2,     3,      2;
    5,    17,     12,      5;
   12,    73,     95,     44,     12;
   33,   369,    721,    512,    168,     33;
   90,  1795,   5487,   5480,   2556,    625,    90;
  261,  9192,  41945,  58990,  36711,  12306,  2342,  261;
  766, 47324, 321951, 625088, 516952, 224241, 57155, 8702, 766;
  ...
From _Gus Wiseman_, Jan 02 2021: (Start)
Non-isomorphic representatives of the 39 = 5 + 17 + 12 + 5 trees with four colored leaves:
  (1111)      (1112)      (1123)      (1234)
  (1(111))    (1122)      (1(123))    (1(234))
  (11(11))    (1(112))    (11(23))    (12(34))
  ((11)(11))  (11(12))    (12(13))    ((12)(34))
  (1(1(11)))  (1(122))    (2(113))    (1(2(34)))
              (11(22))    (23(11))
              (12(11))    ((11)(23))
              (12(12))    (1(1(23)))
              (2(111))    ((12)(13))
              ((11)(12))  (1(2(13)))
              (1(1(12)))  (2(1(13)))
              ((11)(22))  (2(3(11)))
              (1(1(22)))
              (1(2(11)))
              ((12)(12))
              (1(2(12)))
              (2(1(11)))
(End)

Andrew Howroyd, PARI Functions for Combinatorial Species, v2, Dec 2020.
Wikipedia, Combinatorial species

The case with only one color is A000669.
Counting by nodes gives A318231.
A labeled version is A319376.
Row sums are A330470.
A000311 counts singleton-reduced phylogenetic trees.
A001678 counts unlabeled lone-child-avoiding rooted trees.
A005121 counts chains of set partitions, with maximal case A002846.
A005804 counts phylogenetic rooted trees with n labels.
A060356 counts labeled lone-child-avoiding rooted trees.
A141268 counts lone-child-avoiding rooted trees with leaves summing to n.
A291636 lists Matula-Goebel numbers of lone-child-avoiding rooted trees.
A316651 counts lone-child-avoiding rooted trees with normal leaves.
A316652 counts lone-child-avoiding rooted trees with strongly normal leaves.
A330465 counts inequivalent leaf-colorings of phylogenetic rooted trees.
Cf. A196545, A213427, A281118, A289501, A292504, A318812, A319312, A330627.

\\ See link above for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, v[n] = polcoef( sExp(x*Ser(v[1..n])), n )); x*Ser(v)}
{my(A=InequivalentColoringsTriangle(cycleIndexSeries(10))); for(n=1, #A~, print(A[n,1..n]))}

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

Original entry on oeis.org

4, 14, 49, 86, 301, 454, 886, 1589, 1849, 3101, 3986, 6418, 9761, 13766, 13951, 19049, 22463, 26798, 31754, 48181, 51529, 57026, 75266, 85699, 93793, 100561, 111139, 128074, 137987, 196249, 199591, 203878, 263431, 295969, 298154, 302426, 426058, 448259, 452411

Offset: 1

Keith Briggs, Nov 02 2005

nonn

This sequence should probably start with 1. Then a number k is in the sequence iff k = 1 or k = prime(x) * prime(y) with x and y already in the sequence. - Gus Wiseman, May 04 2021

			From _Gus Wiseman_, May 04 2021: (Start)
The sequence of trees (starting with 1) begins:
     1: o
     4: (oo)
    14: (o(oo))
    49: ((oo)(oo))
    86: (o(o(oo)))
   301: ((oo)(o(oo)))
   454: (o((oo)(oo)))
   886: (o(o(o(oo))))
  1589: ((oo)((oo)(oo)))
  1849: ((o(oo))(o(oo)))
  3101: ((oo)(o(o(oo))))
  3986: (o((oo)(o(oo))))
  6418: (o(o((oo)(oo))))
  9761: ((o(oo))((oo)(oo)))
(End)

Kevin Ryde, Table of n, a(n) for n = 1..5000 (terms 1..186 from Charles R Greathouse IV)
Keith Briggs, Matula numbers and rooted trees
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Kevin Ryde, PARI/GP Code
Index entries for sequences related to Matula-Goebel numbers

Cf. A245824 (by number of leaves).
Cf. A005517, A005518, A061773, A245824.
These trees are counted by 2*A001190 - 1.
The semi-binary version is A292050 (counted by A001190).
The semi-identity case is A339193 (counted by A063895).
A000081 counts unlabeled rooted trees with n nodes.
A007097 ranks rooted chains.
A276625 ranks identity trees, counted by A004111.
A306202 ranks semi-identity trees, counted by A306200.
A306203 ranks balanced semi-identity trees, counted by A306201.
A331965 ranks lone-child avoiding semi-identity trees, counted by A331966.
Cf. A036656, A061775, A196050, A291636, A320230, A331935, A331965.

nn=20000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
binQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]===2,And@@binQ/@m]]];
Select[Range[2,nn],binQ] (* Gus Wiseman, Aug 28 2017 *)

i(n)=n==2 || is(primepi(n))
is(n)=if(n<14,return(n==4)); my(f=factor(n),t=#f[,1]); if(t>1, t==2 && f[1,2]==1 && f[2,2]==1 && i(f[1,1]) && i(f[2,1]), f[1,2]==2 && i(f[1,1])) \\ Charles R Greathouse IV, Mar 29 2013

list(lim)=my(v=List(), t); forprime(p=2, sqrt(lim), t=p; forprime(q=p, lim\t, if(i(p)&&i(q), listput(v, t*q)))); vecsort(Vec(v)) \\ Charles R Greathouse IV, Mar 29 2013

PARI
```
\\ Also see links.
```

The Matula tree of k is defined as follows:
matula(k):
    create a node labeled k
    for each prime factor m of k:
       add the subtree matula(prime(m)), by an edge labeled m
    return the node

Definition corrected by Charles R Greathouse IV, Mar 29 2013

a(27)-a(39) from Charles R Greathouse IV, Mar 29 2013

A060356 Expansion of e.g.f.: -LambertW(-x/(1+x)).

Original entry on oeis.org

0, 1, 0, 3, 4, 65, 306, 4207, 38424, 573057, 7753510, 134046671, 2353898196, 47602871329, 1013794852266, 23751106404495, 590663769125296, 15806094859299329, 448284980183376078, 13515502344669830287

Offset: 0

Vladeta Jovovic, Apr 01 2001

Also the number of labeled lone-child-avoiding rooted trees with n nodes. A rooted tree is lone-child-avoiding if it has no unary branchings, meaning every non-leaf node covers at least two other nodes. The unlabeled version is A001678(n + 1). - Gus Wiseman, Jan 20 2020

			From _Gus Wiseman_, Dec 31 2019: (Start)
Non-isomorphic representatives of the a(7) = 4207 trees, written as root[branches], are:
  1[2,3[4,5[6,7]]]
  1[2,3[4,5,6,7]]
  1[2[3,4],5[6,7]]
  1[2,3,4[5,6,7]]
  1[2,3,4,5[6,7]]
  1[2,3,4,5,6,7]
(End)

Harry J. Smith, Table of n, a(n) for n = 0..100
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. A052871, A060313.
Cf. A008297.
Column k=0 of A231602.
The unlabeled version is A001678(n + 1).
The case where the root is fixed is A108919.
Unlabeled rooted trees are counted by A000081.
Lone-child-avoiding rooted trees with labeled leaves are A000311.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Singleton-reduced rooted trees are counted by A330951.
Cf. A000669, A004111, A005121, A048816, A292504, A316651, A316652, A318231, A318813, A330465, A330624.

List([0..20],n->Sum([1..n],k->(-1)^(n-k)*Factorial(n)/Factorial(k) *Binomial(n-1,k-1)*k^(k-1))); # Muniru A Asiru, Feb 19 2018

seq(coeff(series( -LambertW(-x/(1+x)), x, n+1), x, n)*n!, n = 0..20); # G. C. Greubel, Mar 16 2020

CoefficientList[Series[-LambertW[-x/(1+x)], {x, 0, 20}], x]* Range[0, 20]! (* Vaclav Kotesovec, Nov 27 2012 *)
sps[{}]:={{}};sps[set:{i_,_}]:=Join@@Function[s,Prepend[#,s]&/@sps[Complement[set,s]]]/@Cases[Subsets[set],{i,_}];
a[n_]:=If[n==1,1,n*Sum[Times@@a/@Length/@stn,{stn,Select[sps[Range[n-1]],Length[#]>1&]}]];
Array[a,10] (* Gus Wiseman, Dec 31 2019 *)

{ for (n=0, 100, f=n!; a=sum(k=1, n, (-1)^(n - k)*f/k!*binomial(n - 1, k - 1)*k^(k - 1)); write("b060356.txt", n, " ", a); ) } \\ Harry J. Smith, Jul 04 2009

my(x='x+O('x^20)); concat([0], Vec(serlaplace(-lambertw(-x/(1+x))))) \\ G. C. Greubel, Feb 19 2018

a(n) = Sum_{k=1..n} (-1)^(n-k)*n!/k!*binomial(n-1, k-1)*k^(k-1). a(n) = Sum_{k=0..n} Stirling1(n, k)*A058863(k). - Vladeta Jovovic, Sep 17 2003
a(n) ~ n^(n-1) * (1-exp(-1))^(n+1/2). - Vaclav Kotesovec, Nov 27 2012
a(n) = n * A108919(n). - Gus Wiseman, Dec 31 2019

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

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

A292050 Matula-Goebel numbers of semi-binary rooted trees.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 7, 9, 10, 11, 13, 14, 15, 17, 21, 22, 23, 25, 26, 29, 31, 33, 34, 35, 39, 41, 43, 46, 47, 49, 51, 55, 58, 59, 62, 65, 69, 73, 77, 79, 82, 83, 85, 86, 87, 91, 93, 94, 97, 101, 109, 115, 118, 119, 121, 123, 127, 129, 137, 139, 141, 143, 145

Offset: 1

Gus Wiseman, Sep 08 2017

nonn

An unlabeled rooted tree is semi-binary if all out-degrees are <= 2. The number of semi-binary trees with n nodes is equal to the number of binary trees with n+1 leaves; see A001190.

Cf. A000081, A001190, A007097, A036656, A061773, A111299, A214577, A291636.

nn=200;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
semibinQ[n_]:=Or[n===1,With[{m=primeMS[n]},And[Length[m]<=2,And@@semibinQ/@m]]];
Select[Range[nn],semibinQ]

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

A331935 Matula-Goebel numbers of semi-lone-child-avoiding rooted trees.

Original entry on oeis.org

1, 2, 4, 6, 8, 9, 12, 14, 16, 18, 21, 24, 26, 27, 28, 32, 36, 38, 39, 42, 46, 48, 49, 52, 54, 56, 57, 63, 64, 69, 72, 74, 76, 78, 81, 84, 86, 91, 92, 96, 98, 104, 106, 108, 111, 112, 114, 117, 122, 126, 128, 129, 133, 138, 144, 146, 147, 148, 152, 156, 159

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 Matula-Goebel number of a rooted tree is the product of primes indexed by the Matula-Goebel numbers of the branches of its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.
Consists of one, two, and all nonprime numbers whose prime indices already belong to the sequence, where a prime index of n is a number m such that prime(m) divides n.

			The sequence of all semi-lone-child-avoiding rooted trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   4: (oo)
   6: (o(o))
   8: (ooo)
   9: ((o)(o))
  12: (oo(o))
  14: (o(oo))
  16: (oooo)
  18: (o(o)(o))
  21: ((o)(oo))
  24: (ooo(o))
  26: (o(o(o)))
  27: ((o)(o)(o))
  28: (oo(oo))
  32: (ooooo)
  36: (oo(o)(o))
  38: (o(ooo))
  39: ((o)(o(o)))
  42: (o(o)(oo))
The sequence of terms together with their prime indices begins:
    1: {}              46: {1,9}             98: {1,4,4}
    2: {1}             48: {1,1,1,1,2}      104: {1,1,1,6}
    4: {1,1}           49: {4,4}            106: {1,16}
    6: {1,2}           52: {1,1,6}          108: {1,1,2,2,2}
    8: {1,1,1}         54: {1,2,2,2}        111: {2,12}
    9: {2,2}           56: {1,1,1,4}        112: {1,1,1,1,4}
   12: {1,1,2}         57: {2,8}            114: {1,2,8}
   14: {1,4}           63: {2,2,4}          117: {2,2,6}
   16: {1,1,1,1}       64: {1,1,1,1,1,1}    122: {1,18}
   18: {1,2,2}         69: {2,9}            126: {1,2,2,4}
   21: {2,4}           72: {1,1,1,2,2}      128: {1,1,1,1,1,1,1}
   24: {1,1,1,2}       74: {1,12}           129: {2,14}
   26: {1,6}           76: {1,1,8}          133: {4,8}
   27: {2,2,2}         78: {1,2,6}          138: {1,2,9}
   28: {1,1,4}         81: {2,2,2,2}        144: {1,1,1,1,2,2}
   32: {1,1,1,1,1}     84: {1,1,2,4}        146: {1,21}
   36: {1,1,2,2}       86: {1,14}           147: {2,4,4}
   38: {1,8}           91: {4,6}            148: {1,1,12}
   39: {2,6}           92: {1,1,9}          152: {1,1,1,8}
   42: {1,2,4}         96: {1,1,1,1,1,2}    156: {1,1,2,6}

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 enumeration of these trees by leaves is A050381.
The locally disjoint version A331873.
The enumeration of these trees by nodes is A331934.
The case with at most one distinct non-leaf branch of any vertex is A331936.
Lone-child-avoiding rooted trees are counted by A001678.
Matula-Goebel numbers of lone-child-avoiding rooted trees are A291636.
Cf. A000081, A000669, A007097, A061775, A196050, A320269, A330951, A331871, A331872, A331874, A331937, A331965.

mseQ[n_]:=n==1||n==2||!PrimeQ[n]&&And@@mseQ/@PrimePi/@First/@FactorInteger[n];
Select[Range[100],mseQ]

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

A339645 Triangle read by rows: T(n,k) is the number of inequivalent colorings of lone-child-avoiding rooted trees with n colored leaves using exactly k colors.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

A111299 Numbers whose Matula tree is a binary tree (i.e., root has degree 2 and all nodes except root and leaves have degree 3).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

PARI

PARI

Formula

Extensions

A060356 Expansion of e.g.f.: -LambertW(-x/(1+x)).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

GAP

Maple

Mathematica

PARI

PARI

Formula

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