A320230 -id:A320230 - cp's OEIS frontend

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

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

A040039 First differences of A033485; also A033485 with terms repeated.

Original entry on oeis.org

1, 1, 2, 2, 3, 3, 5, 5, 7, 7, 10, 10, 13, 13, 18, 18, 23, 23, 30, 30, 37, 37, 47, 47, 57, 57, 70, 70, 83, 83, 101, 101, 119, 119, 142, 142, 165, 165, 195, 195, 225, 225, 262, 262, 299, 299, 346, 346, 393, 393, 450, 450, 507, 507, 577, 577, 647, 647, 730, 730, 813, 813, 914, 914, 1015, 1015, 1134, 1134, 1253, 1253, 1395, 1395

Offset: 0

N. J. A. Sloane and J. H. Conway

Apparently a(n) = number of partitions (p_1, p_2, ..., p_k) of n+1, with p_1 >= p_2 >= ... >= p_k, such that for each i, p_i > p_{i+1}+...+p_k. - John McKay (mac(AT)mathstat.concordia.ca), Mar 06 2009
Comment from John McKay confirmed in paper by Bessenrodt, Olsson, and Sellers. Such partitions are called "strongly decreasing" partitions in the paper, see the function s(n) therein.
Also the number of unlabeled binary rooted trees with 2*n + 3 nodes in which the two branches directly under any given non-leaf node are either equal or at least one of them is a leaf. - Gus Wiseman, Oct 08 2018
From Gus Wiseman, Apr 06 2021: (Start)
This sequence counts both of the following essentially equivalent things:
1. Sets of distinct positive integers with maximum n + 1 in which all adjacent elements have quotients < 1/2. For example, the a(0) = 1 through a(8) = 7 subsets are:
  {1}  {2}  {3}    {4}    {5}    {6}    {7}      {8}      {9}
            {1,3}  {1,4}  {1,5}  {1,6}  {1,7}    {1,8}    {1,9}
                          {2,5}  {2,6}  {2,7}    {2,8}    {2,9}
                                        {3,7}    {3,8}    {3,9}
                                        {1,3,7}  {1,3,8}  {4,9}
                                                          {1,3,9}
                                                          {1,4,9}
2. Sets of distinct positive integers with maximum n + 1 whose first differences are term-wise greater than their decapitation (remove the maximum). For example, the set q = {1,4,9} has first differences (3,5), which are greater than (1,4), so q is counted under a(8). On the other hand, r = {1,5,9} has first differences (4,4), which are not greater than (1,5), so r is not counted under a(8).
Also the number of partitions of n + 1 into powers of 2 covering an initial interval of powers of 2. For example, the a(0) = 1 through a(8) = 7 partitions are:
  1  11  21   211   221    2211    421      4211      4221
         111  1111  2111   21111   2221     22211     22221
                    11111  111111  22111    221111    42111
                                   211111   2111111   222111
                                   1111111  11111111  2211111
                                                      21111111
                                                      111111111
(End)

			From _Joerg Arndt_, Dec 17 2012: (Start)
The a(19-1)=30 strongly decreasing partitions of 19 are (in lexicographic order)
[ 1]    [ 10 5 3 1 ]
[ 2]    [ 10 5 4 ]
[ 3]    [ 10 6 2 1 ]
[ 4]    [ 10 6 3 ]
[ 5]    [ 10 7 2 ]
[ 6]    [ 10 8 1 ]
[ 7]    [ 10 9 ]
[ 8]    [ 11 5 2 1 ]
[ 9]    [ 11 5 3 ]
[10]    [ 11 6 2 ]
[11]    [ 11 7 1 ]
[12]    [ 11 8 ]
[13]    [ 12 4 2 1 ]
[14]    [ 12 4 3 ]
[15]    [ 12 5 2 ]
[16]    [ 12 6 1 ]
[17]    [ 12 7 ]
[18]    [ 13 4 2 ]
[19]    [ 13 5 1 ]
[20]    [ 13 6 ]
[21]    [ 14 3 2 ]
[22]    [ 14 4 1 ]
[23]    [ 14 5 ]
[24]    [ 15 3 1 ]
[25]    [ 15 4 ]
[26]    [ 16 2 1 ]
[27]    [ 16 3 ]
[28]    [ 17 2 ]
[29]    [ 18 1 ]
[30]    [ 19 ]
The a(20-1)=30 strongly decreasing partitions of 20 are obtained by adding 1 to the first part in each partition in the list.
(End)
From _Gus Wiseman_, Oct 08 2018: (Start)
The a(-1) = 1 through a(4) = 3 semichiral binary rooted trees:
  o  (oo)  (o(oo))  ((oo)(oo))  (o((oo)(oo)))  ((o(oo))(o(oo)))
                    (o(o(oo)))  (o(o(o(oo))))  (o(o((oo)(oo))))
                                               (o(o(o(o(oo)))))
(End)

Seiichi Manyama, Table of n, a(n) for n = 0..10000 (terms 0..500 from Joerg Arndt)
Christine Bessenrodt, Jorn B. Olsson, and James A. Sellers, Unique path partitions: Characterization and Congruences, arXiv:1107.1156 [math.CO], 2011-2012.
J. Jordan and R. Southwell, Further Properties of Reproducing Graphs, Applied Mathematics, Vol. 1 No. 5, 2010, pp. 344-350. - From _N. J. A. Sloane_, Feb 03 2013

Cf. A000123.
Cf. A088567, A089054.
Cf. A001190, A003238, A111299, A292050, A317712, A320222, A320230, A320271.
The equal case is A001511.
The reflected version is A045690.
The unequal (anti-run) version is A045691.
A000929 counts partitions with all adjacent parts x >= 2y.
A002843 counts compositions with all adjacent parts x <= 2y.
A018819 counts partitions into powers of 2.
A154402 counts partitions with all adjacent parts x = 2y.
A274199 counts compositions with all adjacent parts x < 2y.
A342094 counts partitions with all adjacent parts x <= 2y (strict: A342095).
A342096 counts partitions without adjacent x >= 2y (strict: A342097).
A342098 counts partitions with all adjacent parts x > 2y.
A342337 counts partitions with all adjacent parts x = y or x = 2y.
Cf. A000009, A003114, A003242, A224957, A342191, A342330.

# For example, the five partitions of 4, written in nonincreasing order, are
# [1,1,1,1], [2,1,1], [2,2], [3,1], [4].
# Only the last two satisfy the condition, and a(3)=2.
# The Maple program below verifies this for small values of n.
with(combinat); N:=8; a:=array(1..N); c:=array(1..N);
for n from 1 to N do p:=partition(n); np:=nops(p); t:=0;
for s to np do r:=p[s]; r:=sort(r,`>`); nr:=nops(r); j:=1;
while jsum(r[k],k=j+1..nr) do j:=j+1;od; # gives A040039
#while j= sum(r[k],k=j+1..nr) do j:=j+1;od; # gives A018819
if j=nr then t:=t+1;fi od; a[n]:=t; od;
# John McKay

T[n_, m_] := T[n, m] = Sum[Binomial[n-2k-1, n-2k-m] Sum[Binomial[m, i] T[k, i], {i, 1, k}], {k, 0, (n-m)/2}] + Binomial[n-1, n-m];
a[n_] := T[n+1, 1];
Table[a[n], {n, 0, 80}] (* Jean-François Alcover, Jul 27 2018, after Vladimir Kruchinin *)
Table[Length[Select[Subsets[Range[n]],MemberQ[#,n]&&And@@Table[#[[i-1]]/#[[i]]<1/2,{i,2,Length[#]}]&]],{n,15}] (* Gus Wiseman, Apr 06 2021 *)

T(n,m):=sum(binomial(n-2*k-1,n-2*k-m)*sum(binomial(m,i)*T(k,i),i,1,k),k,0,(n-m)/2)+binomial(n-1,n-m);
makelist(T(n+1,1),n,0,40); /* Vladimir Kruchinin, Mar 19 2015 */

/* compute as "A033485 with terms repeated" */
b(n) = if(n<2, 1, b(floor(n/2))+b(n-1));  /* A033485 */
a(n) = b(n\2+1); /* note different offsets */
for(n=0,99, print1(a(n),", ")); /* Joerg Arndt, Jan 21 2011 */

from itertools import islice
from collections import deque
def A040039_gen(): # generator of terms
    aqueue, f, b, a = deque([2]), True, 1, 2
    yield from (1, 1, 2, 2)
    while True:
        a += b
        yield from (a, a)
        aqueue.append(a)
        if f: b = aqueue.popleft()
        f = not f
A040039_list = list(islice(A040039_gen(),40)) # Chai Wah Wu, Jun 07 2022

Let T(x) be the g.f, then T(x) = 1 + x/(1-x)*T(x^2) = 1 + x/(1-x) * ( 1 + x^2/(1-x^2) * ( 1 + x^4/(1-x^4) * ( 1 + x^8/(1-x^8) *(...) ))). [Joerg Arndt, May 11 2010]
From Joerg Arndt, Oct 02 2013: (Start)
G.f.: sum(k>=1, x^(2^k-1) / prod(j=0..k-1, 1-x^(2^k) ) ) [Bessenrodt/Olsson/Sellers].
G.f.: 1/(2*x^2) * ( 1/prod(k>=0, 1 - x^(2^k) ) - (1 + x) ).
a(n) = 1/2 * A018819(n+2).
(End)
a(n) = T(n+1,1), where T(n,m)=sum(k..0,(n-m)/2, binomial(n-2*k-1,n-2*k-m)*sum(i=1..k, binomial(m,i)*T(k,i)))+binomial(n-1,n-m). - Vladimir Kruchinin, Mar 19 2015
Using offset 1: a(1) = 1; a(n even) = a(n-1); a(n odd) = a(n-1) + a((n-1)/2). - Gus Wiseman, Oct 08 2018

A331936 Matula-Goebel numbers of semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex (semi-achirality).

Original entry on oeis.org

1, 2, 4, 6, 8, 9, 12, 14, 16, 18, 24, 26, 27, 28, 32, 36, 38, 46, 48, 49, 52, 54, 56, 64, 72, 74, 76, 81, 86, 92, 96, 98, 104, 106, 108, 112, 122, 128, 144, 148, 152, 162, 169, 172, 178, 184, 192, 196, 202, 206, 208, 212, 214, 216, 224, 243, 244, 256, 262, 288

Offset: 1

Gus Wiseman, Feb 03 2020

nonn

First differs from A331873 in lacking 69, the Matula-Goebel number of the tree ((o)((o)(o))).
A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless that 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 1, 2, and all numbers equal to a power of 2 (other than 1) times a power of prime(j) for some j > 1 already in the sequence.

			The sequence of rooted trees ranked by this sequence 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))
  24: (ooo(o))
  26: (o(o(o)))
  27: ((o)(o)(o))
  28: (oo(oo))
  32: (ooooo)
  36: (oo(o)(o))
  38: (o(ooo))
  46: (o((o)(o)))
  48: (oooo(o))
  49: ((oo)(oo))
The sequence of terms together with their prime indices begins:
    1: {}              52: {1,1,6}            152: {1,1,1,8}
    2: {1}             54: {1,2,2,2}          162: {1,2,2,2,2}
    4: {1,1}           56: {1,1,1,4}          169: {6,6}
    6: {1,2}           64: {1,1,1,1,1,1}      172: {1,1,14}
    8: {1,1,1}         72: {1,1,1,2,2}        178: {1,24}
    9: {2,2}           74: {1,12}             184: {1,1,1,9}
   12: {1,1,2}         76: {1,1,8}            192: {1,1,1,1,1,1,2}
   14: {1,4}           81: {2,2,2,2}          196: {1,1,4,4}
   16: {1,1,1,1}       86: {1,14}             202: {1,26}
   18: {1,2,2}         92: {1,1,9}            206: {1,27}
   24: {1,1,1,2}       96: {1,1,1,1,1,2}      208: {1,1,1,1,6}
   26: {1,6}           98: {1,4,4}            212: {1,1,16}
   27: {2,2,2}        104: {1,1,1,6}          214: {1,28}
   28: {1,1,4}        106: {1,16}             216: {1,1,1,2,2,2}
   32: {1,1,1,1,1}    108: {1,1,2,2,2}        224: {1,1,1,1,1,4}
   36: {1,1,2,2}      112: {1,1,1,1,4}        243: {2,2,2,2,2}
   38: {1,8}          122: {1,18}             244: {1,1,18}
   46: {1,9}          128: {1,1,1,1,1,1,1}    256: {1,1,1,1,1,1,1,1}
   48: {1,1,1,1,2}    144: {1,1,1,1,2,2}      262: {1,32}
   49: {4,4}          148: {1,1,12}           288: {1,1,1,1,1,2,2}

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.

A superset of A000079.
The non-lone-child-avoiding version is A320230.
The non-semi version is A320269.
These trees are counted by A331933.
Not requiring semi-achirality gives A331935.
The fully-achiral case is A331992.
Achiral trees are counted by A003238.
Numbers with at most one distinct odd prime factor are A070776.
Matula-Goebel numbers of achiral rooted trees are A214577.
Matula-Goebel numbers of semi-identity trees are A306202.
Numbers S with at most one distinct prime index in S are A331912.
Cf. A001678, A007097, A050381, A061775, A196050, A291636, A331784, A331873, A331914, A331934, A331965, A331967, A331991.

msQ[n_]:=n<=2||!PrimeQ[n]&&Length[DeleteCases[FactorInteger[n],{2,_}]]<=1&&And@@msQ/@PrimePi/@First/@FactorInteger[n];
Select[Range[100],msQ]

Intersection of A320230 and A331935.

A320222 Number of unlabeled rooted trees with n nodes in which the non-leaf branches directly under any given node are all equal.

Original entry on oeis.org

1, 1, 2, 4, 9, 18, 39, 78, 161, 324, 658, 1316, 2657, 5314, 10668, 21347, 42777, 85554, 171290, 342580, 685498, 1371037, 2742733, 5485466, 10972351, 21944711, 43892080, 87784323, 175574004, 351148008, 702307038, 1404614076, 2809249582, 5618499824, 11237042426

Offset: 1

Gus Wiseman, Oct 07 2018

nonn

This is a weaker condition than achirality (cf. A003238).

			The a(1) = 1 through a(6) = 18 rooted trees:
  o  (o)  (oo)   (ooo)    (oooo)     (ooooo)
          ((o))  ((oo))   ((ooo))    ((oooo))
                 (o(o))   (o(oo))    (o(ooo))
                 (((o)))  (oo(o))    (oo(oo))
                          (((oo)))   (ooo(o))
                          ((o)(o))   (((ooo)))
                          ((o(o)))   ((o(oo)))
                          (o((o)))   ((oo(o)))
                          ((((o))))  (o((oo)))
                                     (o(o)(o))
                                     (o(o(o)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o)(o)))
                                     (((o(o))))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))

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

Cf. A002541, A003238, A010766, A126656, A014668, A167865, A214577, A316782, A317099, A317100, A317712, A320230.

saue[n_]:=Sum[If[SameQ@@DeleteCases[ptn,1],If[DeleteCases[ptn,1]=={},1,saue[DeleteCases[ptn,1][[1]]]],0],{ptn,IntegerPartitions[n-1]}];
Table[saue[n],{n,15}]

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sum(k=2, n-1, (n-1)\k*v[k])); v} \\ Andrew Howroyd, Oct 26 2018

a(n) = 1 + Sum_{k = 2..n-1} floor((n-1)/k) * a(k).

a(n) ~ c * 2^n, where c = 0.3270422384018894564479397100499014525700668391191792769625407295138546463... - Vaclav Kotesovec, Sep 07 2019

A320269 Matula-Goebel numbers of lone-child-avoiding rooted trees in which the non-leaf branches directly under any given node are all equal (semi-achirality).

Original entry on oeis.org

1, 4, 8, 14, 16, 28, 32, 38, 49, 56, 64, 76, 86, 98, 106, 112, 128, 152, 172, 196, 212, 214, 224, 256, 262, 304, 326, 343, 344, 361, 392, 424, 428, 448, 454, 512, 524, 526, 608, 622, 652, 686, 688, 722, 766, 784, 848, 856, 886, 896, 908, 1024, 1042, 1048, 1052

Offset: 1

Gus Wiseman, Oct 08 2018

nonn

First differs from A331871 in lacking 1589.
Lone-child-avoiding means 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 its root, which gives a bijective correspondence between positive integers and unlabeled rooted trees.

			The sequence of rooted trees 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))
   49: ((oo)(oo))
   56: (ooo(oo))
   64: (oooooo)
   76: (oo(ooo))
   86: (o(o(oo)))
   98: (o(oo)(oo))
  106: (o(oooo))
  112: (oooo(oo))
  128: (ooooooo)
  152: (ooo(ooo))
  172: (oo(o(oo)))
  196: (oo(oo)(oo))

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.

Cf. A002541, A070776, A167865, A214577, A317710, A320222, A320226.
The same-tree version is A291441.
Not requiring lone-child-avoidance gives A320230.
The enumeration of these trees by vertices is A320268.
The semi-lone-child-avoiding version is A331936.
If the non-leaf branches are all different instead of equal we get A331965.
The fully-achiral case is A331967.
Achiral rooted trees are counted by A003238.
MG-numbers of lone-child-avoiding rooted trees are A291636.
Cf. A061775, A196050, A276625, A280996, A306202, A331912, A331916, A331966.

primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]
hmakQ[n_]:=And[!PrimeQ[n],SameQ@@DeleteCases[primeMS[n],1],And@@hmakQ/@primeMS[n]];Select[Range[1000],hmakQ[#]&]

Updated with corrected terminology by Gus Wiseman, Feb 06 2020

A331933 Number of semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex.

Original entry on oeis.org

1, 1, 1, 2, 4, 6, 12, 18, 33, 52, 90, 142, 242, 384, 639, 1028, 1688, 2716, 4445, 7161, 11665, 18839, 30595, 49434, 80199, 129637, 210079, 339750, 550228, 889978, 1440909, 2330887, 3772845, 6103823, 9878357, 15982196, 25863454, 41845650, 67713550, 109559443

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(8) = 18 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(o)(o))  (oooo(o))
                                  (o(o(o)))  ((oo)(oo))
                                             (o(o(oo)))
                                             (o(oo(o)))
                                             (oo(o)(o))
                                             (oo(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.
Gus Wiseman, The a(11) = 90 semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex.

Not requiring lone-child-avoidance gives A320222.
The non-semi version is A320268.
Matula-Goebel numbers of these trees are A331936.
Achiral trees are A003238.
Semi-identity trees are A306200.
Numbers S with at most one distinct prime index in S are A331912.
Semi-lone-child-avoiding rooted trees are A331934.
Cf. A000081, A001678, A004111, A050381, A214577, A291636, A320230, A320269, A331784, A331872, A331914, A331935, A331966.

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

seq(n)={my(v=vector(n)); for(n=1, n, v[n] = 1 + sum(i=2, n-2, ((n-1)\i)*v[i])); v} \\ Andrew Howroyd, Feb 09 2020

a(n) = 1 + Sum_{i=2..n-2} floor((n-1)/i)*a(i). - Andrew Howroyd, Feb 09 2020

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

A331967 Matula-Goebel numbers of lone-child-avoiding achiral rooted trees.

Original entry on oeis.org

1, 4, 8, 16, 32, 49, 64, 128, 256, 343, 361, 512, 1024, 2048, 2401, 2809, 4096, 6859, 8192, 16384, 16807, 17161, 32768, 51529, 65536, 96721, 117649, 130321, 131072, 148877, 262144, 516961, 524288, 823543, 1048576, 2097152, 2248091, 2476099, 2621161, 4194304

Offset: 1

Gus Wiseman, Feb 06 2020

nonn

Lone-child-avoiding means there are no unary branchings.
In an achiral rooted tree, the branches of any given vertex are all equal.
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 and all numbers of the form prime(j)^k where k > 1 and j is already in the sequence.

			The sequence of all lone-child-avoiding achiral rooted trees together with their Matula-Goebel numbers begins:
      1: o
      4: (oo)
      8: (ooo)
     16: (oooo)
     32: (ooooo)
     49: ((oo)(oo))
     64: (oooooo)
    128: (ooooooo)
    256: (oooooooo)
    343: ((oo)(oo)(oo))
    361: ((ooo)(ooo))
    512: (ooooooooo)
   1024: (oooooooooo)
   2048: (ooooooooooo)
   2401: ((oo)(oo)(oo)(oo))
   2809: ((oooo)(oooo))
   4096: (oooooooooooo)
   6859: ((ooo)(ooo)(ooo))
   8192: (ooooooooooooo)
  16384: (oooooooooooooo)
  16807: ((oo)(oo)(oo)(oo)(oo))
  17161: ((ooooo)(ooooo))
  32768: (ooooooooooooooo)
  51529: (((oo)(oo))((oo)(oo)))
  65536: (oooooooooooooooo)
  96721: ((oooooo)(oooooo))

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.
Gus Wiseman, The first 30 lone-child-avoiding achiral rooted trees.

A subset of A025475 (nonprime prime powers).
The enumeration of these trees by vertices is A167865.
Not requiring lone-child-avoidance gives A214577.
The semi-achiral version is A320269.
The semi-lone-child-avoiding version is A331992.
Achiral rooted trees are counted by A003238.
MG-numbers of planted achiral rooted trees are A280996.
MG-numbers of lone-child-avoiding rooted trees are A291636.
Cf. A001678, A007097, A061775, A196050, A276625, A291441, A320230, A320268, A331912, A331936, A331963, A331965, A331966, A331991.

msQ[n_]:=n==1||!PrimeQ[n]&&PrimePowerQ[n]&&And@@msQ/@PrimePi/@First/@FactorInteger[n];
Select[Range[10000],msQ]

Intersection of A214577 (achiral) and A291636 (lone-child-avoiding).

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

Original entry on oeis.org

1, 2, 4, 8, 9, 16, 27, 32, 49, 64, 81, 128, 243, 256, 343, 361, 512, 529, 729, 1024, 2048, 2187, 2401, 2809, 4096, 6561, 6859, 8192, 10609, 12167, 16384, 16807, 17161, 19683, 32768, 51529, 59049, 65536, 96721, 117649, 130321, 131072, 148877, 175561, 177147

Offset: 1

Gus Wiseman, Feb 06 2020

nonn

A rooted tree is semi-lone-child-avoiding if there are no vertices with exactly one child unless that child is an endpoint/leaf.
In an achiral rooted tree, the branches of any given vertex are all equal.
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 numbers of the form prime(j)^k where k > 1 and j is already in the sequence.

			The sequence of all semi-lone-child-avoiding achiral rooted trees together with their Matula-Goebel numbers begins:
     1: o
     2: (o)
     4: (oo)
     8: (ooo)
     9: ((o)(o))
    16: (oooo)
    27: ((o)(o)(o))
    32: (ooooo)
    49: ((oo)(oo))
    64: (oooooo)
    81: ((o)(o)(o)(o))
   128: (ooooooo)
   243: ((o)(o)(o)(o)(o))
   256: (oooooooo)
   343: ((oo)(oo)(oo))
   361: ((ooo)(ooo))
   512: (ooooooooo)
   529: (((o)(o))((o)(o)))
   729: ((o)(o)(o)(o)(o)(o))
  1024: (oooooooooo)

Gus Wiseman, Sequences counting series-reduced and lone-child-avoiding trees by number of vertices.
Gus Wiseman, The first 36 semi-lone-child-avoiding achiral rooted trees.

Except for two, a subset of A025475 (nonprime prime powers).
Not requiring achirality gives A331935.
The semi-achiral version is A331936.
The fully-chiral version is A331963.
The semi-chiral version is A331994.
The non-semi version is counted by A331967.
The enumeration of these trees by vertices is A331991.
Achiral rooted trees are counted by A003238.
MG-numbers of achiral rooted trees are A214577.
Cf. A001678, A007097, A050381, A061775, A167865, A196050, A276625, A280996, A291441, A291636, A320230, A320269, A331912, A331933, A331965.

msQ[n_]:=n<=2||!PrimeQ[n]&&Length[FactorInteger[n]]<=1&&And@@msQ/@PrimePi/@First/@FactorInteger[n];
Select[Range[10000],msQ]

Intersection of A214577 (achiral) and A331935 (semi-lone-child-avoiding).

A343663 Number of unlabeled binary rooted semi-identity plane trees with 2*n - 1 nodes.

Original entry on oeis.org

1, 1, 2, 4, 12, 34, 108, 344, 1136, 3796, 12920, 44442, 154596, 542336, 1917648, 6825464, 24439008, 87962312, 318087216, 1155090092, 4210494616, 15400782912, 56508464736, 207935588586, 767162495940, 2837260332472, 10516827106016, 39063666532784, 145378611426512

Offset: 1

Gus Wiseman, May 05 2021

nonn

In a semi-identity tree, only the non-leaf branches of any given vertex are required to be distinct. Alternatively, a rooted tree is a semi-identity tree if the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

			The a(1) = 1 through a(5) = 12 trees:
  o  (oo)  ((oo)o)  (((oo)o)o)  ((((oo)o)o)o)
           (o(oo))  ((o(oo))o)  (((o(oo))o)o)
                    (o((oo)o))  (((oo)o)(oo))
                    (o(o(oo)))  ((o((oo)o))o)
                                ((o(o(oo)))o)
                                ((o(oo))(oo))
                                ((oo)((oo)o))
                                ((oo)(o(oo)))
                                (o(((oo)o)o))
                                (o((o(oo))o))
                                (o(o((oo)o)))
                                (o(o(o(oo))))

Andrew Howroyd, Table of n, a(n) for n = 1..500
Samuele Giraudo, The combinator M and the Mockingbird lattice, arXiv:2204.03586 [math.CO], 2022.
Samuele Giraudo, Mockingbird lattices, Séminaire Lotharingien de Combinatoire XX, Proceedings of the 34th Conf. on Formal Power, Series and Algebraic Combinatorics (Bangalore, India, 2022).

The not necessarily semi-identity version is A000108.
The non-plane version is A063895, ranked by A339193.
The Matula-Goebel numbers in the non-plane case are A339193.
The not-necessarily binary version is A343937.
A000081 counts unlabeled rooted trees with n nodes.
2*A001190 - 1 counts binary trees, ranked by A111299.
A001190 counts semi-binary trees, ranked by A292050.
A004111 counts identity trees, ranked by A276625.
A306200 counts semi-identity trees, ranked by A306202.
A306201 counts balanced semi-identity trees, ranked by A306203.
A331966 counts lone-child avoiding semi-identity trees, ranked by A331965.
Cf. A001678, A320230, A331934, A331963, A331964.

crsiq[n_]:=Join@@Table[Select[Union[Tuples[crsiq/@ptn]],#=={}||#=={{},{}}||Length[#]==2&&(UnsameQ@@DeleteCases[#,{}])&],{ptn,Join@@Permutations/@IntegerPartitions[n-1]}];
Table[Length[crsiq[n]],{n,1,11,2}]
(* Second program: *)
m = 29; p[_] = 1;
Do[p[x_] = 1 + x + x (p[x]^2 - p[x^2]) + O[x]^m // Normal, {m}];
CoefficientList[p[x], x] (* Jean-François Alcover, May 09 2021, after Andrew Howroyd *)

seq(n)={my(p=O(1)); for(n=1, n, p=1 + x + x*(p^2-subst(p,x,x^2))); Vec(p)} \\ Andrew Howroyd, May 07 2021

G.f.: x*A(x) where A(x) satisfies A(x) = 1 + x + x*(A(x)^2 - A(x^2)). - Andrew Howroyd, May 07 2021

Terms a(13) and beyond from Andrew Howroyd, May 07 2021

A320271 Number of unlabeled semi-binary rooted trees with n nodes in which the non-leaf branches directly under any given node are all equal.

Original entry on oeis.org

1, 1, 2, 3, 6, 9, 17, 26, 46, 72, 124, 196, 329, 525, 871, 1396, 2293, 3689, 6028, 9717, 15817, 25534, 41475, 67009, 108680, 175689, 284698, 460387, 745610, 1205997, 1952478, 3158475, 5112349, 8270824, 13385466, 21656290, 35045445, 56701735, 91753208

Offset: 1

Gus Wiseman, Oct 08 2018

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.

			The a(1) = 1 through a(7) = 17 semi-binary rooted trees:
  o  (o)  (oo)   ((oo))   (o(oo))    ((o(oo)))    ((oo)(oo))
          ((o))  (o(o))   (((oo)))   (o((oo)))    (o(o(oo)))
                 (((o)))  ((o)(o))   (o(o(o)))    (((o(oo))))
                          ((o(o)))   ((((oo))))   ((o((oo))))
                          (o((o)))   (((o)(o)))   ((o(o(o))))
                          ((((o))))  (((o(o))))   (o(((oo))))
                                     ((o((o))))   (o((o)(o)))
                                     (o(((o))))   (o((o(o))))
                                     (((((o)))))  (o(o((o))))
                                                  (((((oo)))))
                                                  ((((o)(o))))
                                                  ((((o(o)))))
                                                  (((o))((o)))
                                                  (((o((o)))))
                                                  ((o(((o)))))
                                                  (o((((o)))))
                                                  ((((((o))))))

Cf. A001190, A003238, A111299, A126656, A292050, A298204, A301345, A317712, A320222, A320230, A320270.

crb[n_]:=Switch[n,1,1,2,1,3,2,?EvenQ,crb[n-1]+crb[n-2],?OddQ,crb[n-1]+crb[n-2]+crb[(n-1)/2]]
Array[crb,20]

       a(1) = 1,
       a(2) = 1,
       a(3) = 2,
  a(n even) = a(n-1) + a(n-2),
   a(n odd) = a(n-1) + a(n-2) + a((n-1)/2).

cp's OEIS Frontend

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

A040039 First differences of A033485; also A033485 with terms repeated.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Maxima

PARI

Python

Formula

A331936 Matula-Goebel numbers of semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex (semi-achirality).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A320222 Number of unlabeled rooted trees with n nodes in which the non-leaf branches directly under any given node are all equal.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

A320269 Matula-Goebel numbers of lone-child-avoiding rooted trees in which the non-leaf branches directly under any given node are all equal (semi-achirality).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Extensions

A331933 Number of semi-lone-child-avoiding rooted trees with at most one distinct non-leaf branch directly under any vertex.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A331967 Matula-Goebel numbers of lone-child-avoiding achiral rooted trees.

Views