A111299 -id:A111299 - cp's OEIS frontend

A298479 Matula-Goebel numbers of rooted trees in which all positive outdegrees are different.

1, 2, 4, 6, 7, 8, 12, 16, 19, 24, 28, 32, 38, 42, 48, 52, 53, 56, 57, 64, 68, 74, 84, 96, 104, 106, 107, 112, 128, 131, 134, 136, 152, 159, 163, 168, 178, 192, 208, 212, 224, 228, 256, 262, 263, 272, 296, 304, 311, 318, 336, 356, 384, 393, 416, 446, 448, 456

Offset: 1

Gus Wiseman, Jan 19 2018

nonn

			Sequence of trees begins:
1  o
2  (o)
4  (oo)
6  (o(o))
7  ((oo))
8  (ooo)
12 (oo(o))
16 (oooo)
19 ((ooo))
24 (ooo(o))
28 (oo(oo))
32 (ooooo)
38 (o(ooo))
42 (o(o)(oo))
48 (oooo(o))
52 (oo(o(o)))
53 ((oooo))
56 (ooo(oo))
57 ((o)(ooo))
64 (oooooo)
68 (oo((oo)))
74 (o(oo(o)))
84 (oo(o)(oo))
96 (ooooo(o))

Cf. A000081, A001221, A004111, A007097, A032305, A061775, A111299, A276625, A290760, A297571, A298120, A298422, A298424, A298478.

MGtree[n_]:=If[n===1,{},MGtree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
doQ[n_]:=Or[n===1,UnsameQ@@Length/@Cases[MGtree[n],{},{0,Infinity}]];
Select[Range[1000],doQ]

A317097 Number of rooted trees with n nodes where the number of distinct branches under each node is <= 2.

Original entry on oeis.org

1, 1, 2, 4, 9, 20, 46, 106, 248, 583, 1393, 3343, 8111, 19801, 48719, 120489, 299787, 749258, 1881216, 4741340, 11993672, 30436507, 77471471, 197726053, 505917729, 1297471092, 3334630086, 8587369072, 22155278381, 57259037225, 148222036272, 384272253397

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

There can be more than two branches as long as there are not three distinct branches.

			The a(5) = 9 trees:
  ((((o))))
  (((oo)))
  ((o(o)))
  ((ooo))
  (o((o)))
  (o(oo))
  ((o)(o))
  (oo(o))
  (oooo)

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

Cf. A000081, A000598, A001190, A003238, A055277, A111299, A292050, A298204, A301344, A317098.

semisameQ[u_]:=Length[Union[u]]<=2;
nms[n_]:=nms[n]=If[n==1,{{}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],semisameQ],{ptn,IntegerPartitions[n-1]}]];
Table[Length[nms[n]],{n,10}]

seq(n)={my(v=vector(n)); v[1]=1; for(n=1, n-1, v[n+1]=sum(k=1, n-1, sumdiv(k, d, v[d])*sumdiv(n-k, d, v[d])/2) + sumdiv(n, d, v[n/d]*(1 - (d-1)/2)) ); v} \\ Andrew Howroyd, Aug 28 2018

Terms a(20) and beyond from Andrew Howroyd, Aug 28 2018

A317098 Number of series-reduced rooted trees with n unlabeled leaves where the number of distinct branches under each node is <= 2.

Original entry on oeis.org

1, 1, 2, 5, 12, 31, 80, 214, 576, 1595, 4448, 12625, 36146, 104662, 305251, 897417, 2654072, 7895394, 23601441, 70871693, 213660535, 646484951, 1962507610, 5975425743, 18243789556, 55841543003, 171320324878, 526738779846, 1622739134873, 5008518981670

Offset: 1

Gus Wiseman, Aug 01 2018

nonn

There can be more than two branches as long as there are not three distinct branches.

			The a(5) = 12 trees:
  (o(o(o(oo))))
  (o(o(ooo)))
  (o((oo)(oo)))
  (o(oo(oo)))
  (o(oooo))
  ((oo)(o(oo)))
  ((oo)(ooo))
  (oo(o(oo)))
  (oo(ooo))
  (o(oo)(oo))
  (ooo(oo))
  (ooooo)

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

Cf. A000081, A000598, A001190, A055277, A111299, A292050, A298204, A301344, A317097.

semisameQ[u_]:=Length[Union[u]]<=2;
nms[n_]:=nms[n]=If[n==1,{{1}},Join@@Table[Select[Union[Sort/@Tuples[nms/@ptn]],semisameQ],{ptn,Rest[IntegerPartitions[n]]}]];
Table[Length[nms[n]],{n,10}]

seq(n)={my(v=vector(n)); v[1]=1; for(n=2, n, v[n]=sum(k=1, n-1, sumdiv(k, d, v[d])*sumdiv(n-k, d, v[d])/2) + sumdiv(n, d, v[n/d]*(1 - (d-1)/2)) ); v} \\ Andrew Howroyd, Aug 19 2018

Terms a(21) and beyond from Andrew Howroyd, Aug 19 2018

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

A343937 Number of unlabeled semi-identity plane trees with n nodes.

Original entry on oeis.org

1, 1, 2, 5, 13, 38, 117, 375, 1224, 4095, 13925, 48006, 167259, 588189, 2084948, 7442125, 26725125, 96485782, 350002509, 1275061385, 4662936808, 17111964241, 62996437297, 232589316700, 861028450579, 3195272504259, 11884475937910, 44295733523881, 165420418500155

Offset: 1

Gus Wiseman, May 07 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 iff the non-leaf branches of the root are all distinct and are themselves semi-identity trees.

			The a(1) = 1 through a(5) = 13 trees are the following. The number of nodes is the number of o's plus the number of brackets (...).
  o  (o)  (oo)   (ooo)    (oooo)
          ((o))  ((o)o)   ((o)oo)
                 ((oo))   ((oo)o)
                 (o(o))   ((ooo))
                 (((o)))  (o(o)o)
                          (o(oo))
                          (oo(o))
                          (((o))o)
                          (((o)o))
                          (((oo)))
                          ((o(o)))
                          (o((o)))
                          ((((o))))

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

The not necessarily semi-identity version is A000108.
The non-plane binary version is A063895, ranked by A339193.
The non-plane version is A306200, ranked by A306202.
The binary case is A343663.
A000081 counts unlabeled rooted trees with n nodes.
A001190*2 - 1 counts binary trees, ranked by A111299.
A001190 counts semi-binary trees, ranked by A292050.
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, A320230, A331934, A331963, A331964.

arsiq[n_]:=Join@@Table[Select[Union[Tuples[arsiq/@ptn]],#=={}||(UnsameQ@@DeleteCases[#,{}])&],{ptn,Join@@Permutations/@IntegerPartitions[n-1]}];
Table[Length[arsiq[n]],{n,10}]

F(p)={my(n=serprec(p,x)-1, q=exp(x*y + O(x*x^n))*prod(k=2, n, (1 + y*x^k + O(x*x^n))^polcoef(p,k,x)) ); sum(k=0, n, k!*polcoef(q,k,y))}
seq(n)={my(p=O(x)); for(n=1, n, p=x*F(p)); Vec(p)} \\ Andrew Howroyd, May 08 2021

G.f.: A(x) satisfies A(x) = x*Sum_{j>=0} j!*[y^j] exp(x*y - Sum_{k>=1} (-y)^k*(A(x^k) - x^k)/k). - Andrew Howroyd, May 08 2021

Terms a(17) and beyond from Andrew Howroyd, May 08 2021

A298540 Matula-Goebel numbers of rooted trees such that every branch of the root has a different number of nodes.

Original entry on oeis.org

1, 2, 3, 5, 6, 7, 10, 11, 13, 14, 15, 17, 19, 21, 22, 23, 26, 29, 30, 31, 33, 34, 37, 38, 39, 41, 42, 43, 46, 47, 51, 53, 55, 57, 58, 59, 61, 62, 65, 66, 67, 69, 71, 73, 74, 77, 78, 79, 82, 83, 85, 86, 87, 89, 91, 93, 94, 95, 97, 101, 102, 103, 106, 107, 109

Offset: 1

Gus Wiseman, Jan 21 2018

nonn

			Sequence of trees begins:
1  o
2  (o)
3  ((o))
5  (((o)))
6  (o(o))
7  ((oo))
10 (o((o)))
11 ((((o))))
13 ((o(o)))
14 (o(oo))
15 ((o)((o)))
17 (((oo)))
19 ((ooo))
21 ((o)(oo))
22 (o(((o))))
23 (((o)(o)))
26 (o(o(o)))
29 ((o((o))))
30 (o(o)((o)))

Cf. A000081, A007097, A061775, A111299, A214577, A276625, A290760, A291442, A297571, A298479, A298534, A298536, A298538, A298539.

nn=500;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
MGweight[n_]:=If[n===1,1,1+Total[MGweight/@primeMS[n]]];
Select[Range[nn],UnsameQ@@MGweight/@primeMS[#]&]

A352456 Smallest Matula-Goebel number of a rooted binary tree (everywhere 0 or 2 children) of n childless vertices.

Original entry on oeis.org

1, 4, 14, 49, 301, 1589, 9761, 51529, 452411, 3041573, 23140153, 143573641, 1260538619, 8474639717, 64474684537

Offset: 1

Kevin Ryde, Mar 16 2022

In the formula below, the two subtrees of the root have x and y childless vertices. The minimum Matula-Goebel number for that partition uses the minimum numbers for each subtree. The question is then which x+y partition is the overall minimum.

			For n = 6, the tree a(6) = 1589 is
.
        *   root
     /    \
    *      *       6 childless
   / \    / \      vertices "@"
  @  @   *   *
        / \ / \
        @ @ @ @
.

Audace A. V. Dossou-Olory. The topological trees with extreme Matula numbers. J. Combin. Math. Combin. Comput., 115 (2020), 215-225.

Audace Amen Vioutou Dossou-Olory, The topological trees with extremal Matula numbers, arXiv:1806.03995 [math.CO], 2018.
Kevin Ryde, PARI/GP Code
Index entries for sequences related to Matula-Goebel numbers

Column 1 of A245824.

Cf. A111299 (all binary trees), A005517 (smallest all trees), A000040 (primes).

PARI
```
\\ See links.
```

from sympy import prime
from itertools import count, islice
def agen(): # generator of terms
    alst, plst = [0, 1], [0, 2]
    yield 1
    for n in count(2):
        an = min(plst[x]*plst[n-x] for x in range(1, n//2+1))
        yield an
        alst.append(an)
        plst.append(prime(an))
print(list(islice(agen(), 10))) # Michael S. Branicky, Mar 17 2022

a(n) = Min_{x+y=n} prime(a(x))*prime(a(y)).

a(14) from Michael S. Branicky, Mar 17 2022

a(15) from Andrew Howroyd, Sep 17 2023

A356121 Matula-Goebel number of the rooted binary tree with Colijn-Plazzotta number n.

Original entry on oeis.org

1, 4, 14, 49, 86, 301, 1849, 454, 1589, 9761, 51529, 886, 3101, 19049, 100561, 196249, 3986, 13951, 85699, 452411, 882899, 3972049, 31754, 111139, 682711, 3604079, 7033511, 31642861, 252079129, 6418, 22463, 137987, 728443, 1421587, 6395537, 50949293, 10297681

Offset: 1

Kevin Ryde, Jul 31 2022

nonn

A permutation of A111299.

C. Colijn and G. Plazzotta, A Metric on Phylogenetic Tree Shapes, Systematic Biology, volume 67, number 1, January 2018, pages 113-126.
F. Goebel, On a 1-1-Correspondence between Rooted Trees and Natural Numbers, Journal of Combinatorial Theory, series B, volume 29, 1980, pages 141-143.
D. W. Matula, A Natural Rooted Tree Enumeration By Prime Factorization, SIAM Review, volume 10, number 2, April 1968, page 273 (also at JSTOR).
Kevin Ryde, PARI/GP Code
Index entries for sequences related to Matula-Goebel numbers

Cf. A002024, A002260, A111299.

PARI
```
\\ See links.
```

a(n) = prime(a(x)) * prime(a(y)) for n>=2, where subtrees x = A002024(n-1) and y = A002260(n-1).

A298363 Matula-Goebel numbers of rooted identity trees with thinning limbs.

Original entry on oeis.org

1, 2, 3, 5, 6, 10, 11, 15, 22, 26, 30, 31, 33, 39, 55, 58, 62, 65, 66, 78, 87, 93, 94, 110, 127, 130, 141, 143, 145, 155, 158, 165, 174, 186, 195, 202, 235, 237, 254, 274, 282, 286, 290, 303, 310, 319, 330, 334, 341, 377, 381, 390, 395, 403, 411, 429, 435, 465

Offset: 1

Gus Wiseman, Jan 17 2018

nonn

An unlabeled rooted tree has thinning limbs if its outdegrees are weakly decreasing from root to leaves.

			Sequence of trees begins:
1  o
2  (o)
3  ((o))
5  (((o)))
6  (o(o))
10 (o((o)))
11 ((((o))))
15 ((o)((o)))
22 (o(((o))))
26 (o(o(o)))
30 (o(o)((o)))
31 (((((o)))))
33 ((o)(((o))))
39 ((o)(o(o)))
55 (((o))(((o))))
58 (o(o((o))))
62 (o((((o)))))
65 (((o))(o(o)))
66 (o(o)(((o))))
78 (o(o)(o(o)))
87 ((o)(o((o))))
93 ((o)((((o)))))
94 (o((o)((o))))

Cf. A000081, A004111, A007097, A061775, A111299, A124343, A124346, A214577, A276625, A277098, A290689, A290760, A298304, A298305.

MGtree[n_]:=If[n===1,{},MGtree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
idthinQ[t_]:=And@@Cases[t,b_List:>UnsameQ@@b&&Length[b]>=Max@@Length/@b,{0,Infinity}];
Select[Range[500],idthinQ[MGtree[#]]&]

Intersection of A276625 and A298303.

A317720 Numbers that are not uniform relatively prime tree numbers.

Original entry on oeis.org

9, 12, 18, 20, 21, 23, 24, 25, 27, 28, 37, 39, 40, 44, 45, 46, 48, 49, 50, 52, 54, 56, 57, 60, 61, 63, 65, 68, 69, 71, 72, 73, 74, 75, 76, 80, 81, 83, 84, 87, 88, 89, 90, 91, 92, 96, 97, 98, 99, 103, 104, 107, 108, 111, 112, 115, 116, 117, 120, 121, 122, 124

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

A positive integer n is a uniform relatively prime tree number iff either n = 1 or n is a prime number whose prime index is a uniform relatively prime tree number, or n is a power of a squarefree number whose prime indices are relatively prime and are themselves uniform relatively prime tree numbers. A prime index of n is a number m such that prime(m) divides n.

			The sequence of non-uniform tree numbers together with their Matula-Goebel trees begins:
   9: ((o)(o))
  12: (oo(o))
  18: (o(o)(o))
  20: (oo((o)))
  21: ((o)(oo))
  23: (((o)(o)))
  24: (ooo(o))
  25: (((o))((o)))
  27: ((o)(o)(o))
  28: (oo(oo))
  37: ((oo(o)))
  39: ((o)(o(o)))
  40: (ooo((o)))
  44: (oo(((o))))
  45: ((o)(o)((o)))

Cf. A061775, A072774, A111299, A214577, A276625, A277098, A303431, A317590.

Cf. A317705, A317707, A317708, A317709, A317710, A317712, A317717, A317718.

rupQ[n_]:=Or[n==1,If[PrimeQ[n],rupQ[PrimePi[n]],And[SameQ@@FactorInteger[n][[All,2]],GCD@@PrimePi/@FactorInteger[n][[All,1]]==1,And@@rupQ/@PrimePi/@FactorInteger[n][[All,1]]]]];
Select[Range[200],!rupQ[#]&]

cp's OEIS Frontend

A298479 Matula-Goebel numbers of rooted trees in which all positive outdegrees are different.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A317097 Number of rooted trees with n nodes where the number of distinct branches under each node is <= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

A317098 Number of series-reduced rooted trees with n unlabeled leaves where the number of distinct branches under each node is <= 2.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Extensions

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.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

Formula

A343937 Number of unlabeled semi-identity plane trees with n nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A298540 Matula-Goebel numbers of rooted trees such that every branch of the root has a different number of nodes.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A352456 Smallest Matula-Goebel number of a rooted binary tree (everywhere 0 or 2 children) of n childless vertices.

Views

Author

Keywords

Comments

Examples

References

Links

Crossrefs

Programs

PARI

Python

Formula

Extensions

A356121 Matula-Goebel number of the rooted binary tree with Colijn-Plazzotta number n.

Views