A111299 -id:A111299 - cp's OEIS frontend

A317711 Numbers that are not uniform tree numbers.

12, 18, 20, 24, 28, 37, 40, 44, 45, 48, 50, 52, 54, 56, 60, 61, 63, 68, 71, 72, 74, 75, 76, 80, 84, 88, 89, 90, 92, 96, 98, 99, 104, 107, 108, 111, 112, 116, 117, 120, 122, 124, 126, 132, 135, 136, 140, 142, 144, 147, 148, 150, 152, 153, 156, 157, 160, 162

Offset: 1

Gus Wiseman, Aug 05 2018

nonn

A positive integer n is a uniform tree number iff either n = 1 or n is a power of a squarefree number whose prime indices are also uniform 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:
  12: (oo(o))
  18: (o(o)(o))
  20: (oo((o)))
  24: (ooo(o))
  28: (oo(oo))
  37: ((oo(o)))
  40: (ooo((o)))
  44: (oo(((o))))
  45: ((o)(o)((o)))
  48: (oooo(o))
  50: (o((o))((o)))
  52: (oo(o(o)))
  54: (o(o)(o)(o))
  56: (ooo(oo))
  60: (oo(o)((o)))

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

Cf. A317705, A317707, A317708, A317709, A317710 (complement), A317712, A317717, A317718.

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

A301344 Regular triangle where T(n,k) is the number of semi-binary rooted trees with n nodes and k leaves.

Original entry on oeis.org

1, 1, 0, 1, 1, 0, 1, 2, 0, 0, 1, 4, 1, 0, 0, 1, 6, 4, 0, 0, 0, 1, 9, 11, 2, 0, 0, 0, 1, 12, 24, 9, 0, 0, 0, 0, 1, 16, 46, 32, 3, 0, 0, 0, 0, 1, 20, 80, 86, 20, 0, 0, 0, 0, 0, 1, 25, 130, 203, 86, 6, 0, 0, 0, 0, 0, 1, 30, 200, 423, 283, 46, 0, 0, 0, 0, 0, 0, 1, 36, 295, 816, 786, 234, 11, 0, 0, 0, 0

Offset: 1

Gus Wiseman, Mar 19 2018

A rooted tree is semi-binary if all outdegrees 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.

			Triangle begins:
1
1   0
1   1   0
1   2   0   0
1   4   1   0   0
1   6   4   0   0   0
1   9  11   2   0   0   0
1  12  24   9   0   0   0   0
1  16  46  32   3   0   0   0   0
1  20  80  86  20   0   0   0   0   0
1  25 130 203  86   6   0   0   0   0   0
The T(6,3) = 4 semi-binary rooted trees: ((o(oo))), (o((oo))), (o(o(o))), ((o)(oo)).

Cf. A000081, A000598, A001190, A001678, A003238, A004111, A055277, A111299, A273873, A290689, A291636, A292050, A298118, A298204, A298422, A298426, A301342, A301343, A301345.

rbt[n_]:=rbt[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[rbt/@c]]]/@Select[IntegerPartitions[n-1],Length[#]<=2&]];
Table[Length[Select[rbt[n],Count[#,{},{-2}]===k&]],{n,15},{k,n}]

A298424 Matula-Goebel numbers of rooted trees in which all positive outdegrees are the same.

Original entry on oeis.org

1, 2, 3, 4, 5, 8, 11, 14, 16, 31, 32, 49, 64, 76, 86, 127, 128, 256, 301, 424, 454, 512, 709, 722, 886, 1024, 1532, 1589, 1849, 2048, 2096, 3101, 3986, 4096, 5381, 6418, 6859, 8192, 9761, 9952, 11236, 13766, 13951, 14554, 16384, 19049, 21884, 22463, 23512

Offset: 1

Gus Wiseman, Jan 19 2018

nonn

			Sequence of trees begins:
1   o
2   (o)
3   ((o))
4   (oo)
5   (((o)))
8   (ooo)
11  ((((o))))
14  (o(oo))
16  (oooo)
31  (((((o)))))
32  (ooooo)
49  ((oo)(oo))
64  (oooooo)
76  (oo(ooo))
86  (o(o(oo)))
127 ((((((o))))))
128 (ooooooo)
256 (oooooooo)
301 ((oo)(o(oo)))
424 (ooo(oooo))
454 (o((oo)(oo)))
512 (ooooooooo)
709 (((((((o)))))))
722 (o(ooo)(ooo))
886 (o(o(o(oo))))

Cf. A000081, A000598, A001190, A003238, A007097, A111299, A214577, A276625, A298422, A298423, A298426.

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

A318230 Number of inequivalent leaf-colorings of binary rooted trees with 2n + 1 nodes.

Original entry on oeis.org

1, 2, 4, 18, 79, 474, 3166, 24451, 208702, 1958407, 19919811, 217977667, 2547895961, 31638057367, 415388265571, 5743721766718, 83356613617031, 1265900592208029, 20064711719120846, 331153885800672577, 5679210649417608867, 101017359002718628295, 1860460510677429522171

Offset: 0

Gus Wiseman, Aug 21 2018

nonn

			Inequivalent representatives of the a(3) = 18 leaf-colorings of binary rooted trees with 7 nodes:
  (1(1(11)))  ((11)(11))
  (1(1(12)))  ((11)(12))
  (1(1(22)))  ((11)(22))
  (1(1(23)))  ((11)(23))
  (1(2(11)))  ((12)(12))
  (1(2(12)))  ((12)(13))
  (1(2(13)))  ((12)(34))
  (1(2(22)))
  (1(2(23)))
  (1(2(33)))
  (1(2(34)))

Andrew Howroyd, Table of n, a(n) for n = 0..49

Cf. A000081, A001190, A001678, A003238, A004111, A111299, A290689, A304486.

Cf. A318226, A318227, A318228, A318229, A318231, A318234, A319590, A339645.

\\ See links in A339645 for combinatorial species functions.
cycleIndexSeries(n)={my(v=vector(n)); v[1]=sv(1); for(n=2, #v, my(p=x*Ser(v[1..n-1])); v[n]=polcoef(p^2 + if(n%2==0, sRaise(p,2)), n)/2); x*Ser(v)}
InequivalentColoringsSeq(cycleIndexSeries(20)) \\ Andrew Howroyd, Dec 11 2020

Terms a(5) and beyond from Andrew Howroyd, Dec 10 2020

A358375 Numbers k such that the k-th standard ordered rooted tree is binary.

Original entry on oeis.org

1, 4, 18, 25, 137, 262146, 393217, 2097161, 2228225

Offset: 1

Gus Wiseman, Nov 14 2022

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 initial terms and their corresponding trees:
       1: o
       4: (oo)
      18: ((oo)o)
      25: (o(oo))
     137: ((oo)(oo))
  262146: (((oo)o)o)
  393217: (o((oo)o))

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

The unordered version is A111299, counted by A001190
These trees are counted by A126120.
A000081 counts unlabeled rooted trees, ranked by A358378.
A358371 and A358372 count leaves and nodes in standard ordered rooted trees.
Cf. A001263, A004249, A005043, A063895, A245824, A284778, A358373, A358374, A358376, A358377.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
Select[Range[1000],FreeQ[srt[#],[_]?(Length[#]!=2&)]&]

A245824 Triangle read by rows: row n>=1 contains in increasing order the Matula numbers of the rooted binary trees with n leaves.

Original entry on oeis.org

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

Offset: 1

Emeric Deutsch, Aug 02 2014

The Matula-Goebel number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.

Row n contains A001190(n) entries (the Wedderburn-Etherington numbers).

			Row 2 is: 4 (the Matula number of the rooted tree V)
Triangle starts:
1;
4;
14;
49, 86;
301, 454, 886;
1589, 1849, 3101, 3986, 6418, 13766;

Gus Wiseman, Table of n, a(n) for n = 1..94
Emeric Deutsch, Tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], (18-November-2011)
Emeric Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.

Cf. A000081, A001190, A007097, A061773, A111299 (the ordered sequence of all numbers appearing in this sequence), A280994.

nn=9;
allbin[n_]:=allbin[n]=If[n===1,{{}},Join@@Function[c,Union[Sort/@Tuples[allbin/@c]]]/@Select[IntegerPartitions[n-1],Length[#]===2&]];
MGNumber[{}]:=1;MGNumber[x:{}]:=Times@@Prime/@MGNumber/@x;
Table[Sort[MGNumber/@allbin[n]],{n,1,2nn,2}] (* Gus Wiseman, Aug 28 2017 *)

Let H[n] denote the set of binary rooted trees with n leaves or, with some abuse, the set of their Matula numbers (for example, H[1]={1}, H[2]={4}). Each binary rooted tree with n leaves is obtained by identifying the roots of an "elevated" tree from H[k] and of an "elevated" tree from H[n-k] (k=1,..., floor(n/2)). The Maple program is based on this. It makes use of the fact that the Matula number of the "elevation" of a rooted tree with Matula number q has Matula number equal to the q-th prime. The shown program determines H[m] for m=3...9 but shows only H[9].

Ordering of terms corrected by Gus Wiseman, Aug 29 2017

A303024 Matula-Goebel numbers of anti-binary (no binary branchings) rooted trees.

Original entry on oeis.org

1, 2, 3, 5, 8, 11, 12, 16, 18, 19, 20, 24, 27, 30, 31, 32, 36, 37, 40, 44, 45, 48, 50, 53, 54, 60, 61, 64, 66, 67, 71, 72, 75, 76, 80, 81, 88, 89, 90, 96, 99, 100, 103, 108, 110, 113, 114, 120, 124, 125, 127, 128, 131, 132, 135, 144, 148, 150, 151, 152, 157

Offset: 1

Gus Wiseman, Aug 15 2018

nonn

			The sequence of anti-binary rooted trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   5: (((o)))
   8: (ooo)
  11: ((((o))))
  12: (oo(o))
  16: (oooo)
  18: (o(o)(o))
  19: ((ooo))
  20: (oo((o)))
  24: (ooo(o))
  27: ((o)(o)(o))
  30: (o(o)((o)))
  31: (((((o)))))

Cf. A000081, A000598, A001190, A001678, A007097, A061775, A111299, A292050, A298422, A298424.

Cf. A303022, A303023, A303025, A303026, A303027.

abQ[n_]:=Or[n==1,And[PrimeOmega[n]!=2,And@@Cases[FactorInteger[n],{p_,_}:>abQ[PrimePi[p]]]]]
Select[Range[100],abQ]

A318612 Matula-Goebel numbers of powerful rooted trees.

Original entry on oeis.org

1, 2, 3, 4, 5, 7, 8, 9, 11, 16, 17, 19, 23, 25, 27, 31, 32, 36, 49, 53, 59, 64, 67, 72, 81, 83, 97, 100, 103, 108, 121, 125, 127, 128, 131, 144, 151, 196, 200, 216, 225, 227, 241, 243, 256, 277, 288, 289, 311, 324, 331, 343, 359, 361, 392, 400, 419, 431, 432

Offset: 1

Gus Wiseman, Aug 30 2018

nonn

A prime index of n is a number m such that prime(m) divides n. A positive integer n is a Matula-Goebel number of a powerful rooted tree iff either n = 1 or n is a prime number whose prime index is a Matula-Goebel number of a powerful rooted tree or n is a powerful number (meaning its prime multiplicities are all greater than 1) whose prime indices are all Matula-Goebel numbers of powerful rooted trees.

			The sequence of all powerful rooted trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   7: ((oo))
   8: (ooo)
   9: ((o)(o))
  11: ((((o))))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  23: (((o)(o)))
  25: (((o))((o)))
  27: ((o)(o)(o))
  31: (((((o)))))

Complement of A317719.

Cf. A000081, A001694, A061775, A111299, A214577, A276625, A303431, A317102, A317705, A317707.

powgoQ[n_]:=Or[n==1,If[PrimeQ[n],powgoQ[PrimePi[n]],And[Min@@FactorInteger[n][[All,2]]>1,And@@powgoQ/@PrimePi/@FactorInteger[n][[All,1]]]]];
Select[Range[1000],powgoQ]

A298305 Matula-Goebel numbers of rooted trees with strictly thinning limbs.

Original entry on oeis.org

1, 2, 4, 6, 8, 9, 12, 16, 18, 24, 27, 28, 32, 36, 42, 48, 52, 54, 56, 63, 64, 72, 78, 81, 84, 92, 96, 98, 104, 108, 112, 117, 126, 128, 138, 144, 147, 152, 156, 162, 168, 182, 184, 189, 192, 196, 207, 208, 216, 224, 228, 234, 243, 252, 256, 273, 276, 288, 294

Offset: 1

Gus Wiseman, Jan 16 2018

nonn

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

			Sequence of trees begins:
1  o
2  (o)
4  (oo)
6  (o(o))
8  (ooo)
9  ((o)(o))
12 (oo(o))
16 (oooo)
18 (o(o)(o))
24 (ooo(o))
27 ((o)(o)(o))
28 (oo(oo))
32 (ooooo)
36 (oo(o)(o))
42 (o(o)(oo))
48 (oooo(o))
52 (oo(o(o)))
54 (o(o)(o)(o))
56 (ooo(oo))
63 ((o)(o)(oo))
64 (oooooo)
72 (ooo(o)(o))
78 (o(o)(o(o)))
81 ((o)(o)(o)(o))
84 (oo(o)(oo))
92 (oo((o)(o)))
96 (ooooo(o))
98 (o(oo)(oo))

Cf. A000081, A007097, A061775, A111299, A124343, A124346, A214577, A276625, A290760, A291636, A298126, A298120, A298304.

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

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

Original entry on oeis.org

1, 2, 3, 5, 7, 11, 13, 14, 17, 19, 21, 23, 26, 29, 31, 34, 35, 37, 38, 39, 41, 43, 46, 47, 51, 53, 57, 58, 59, 61, 65, 67, 69, 71, 73, 74, 77, 79, 82, 83, 85, 86, 87, 89, 94, 95, 97, 101, 103, 106, 107, 109, 111, 113, 115, 118, 122, 123, 127, 129, 131, 133

Offset: 1

Gus Wiseman, Jan 20 2018

nonn

			Sequence of trees begins:
1  o
2  (o)
3  ((o))
5  (((o)))
7  ((oo))
11 ((((o))))
13 ((o(o)))
14 (o(oo))
17 (((oo)))
19 ((ooo))
21 ((o)(oo))
23 (((o)(o)))
26 (o(o(o)))
29 ((o((o))))
31 (((((o)))))
34 (o((oo)))
35 (((o))(oo))
37 ((oo(o)))
38 (o(ooo))
39 ((o)(o(o)))
41 (((o(o))))
43 ((o(oo)))
46 (o((o)(o)))
47 (((o)((o))))

Cf. A000081, A007097, A061775, A111299, A214577, A276625, A290689, A290760, A291442, A298534, A298535.

nn=2000;
primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
leafcount[n_]:=If[n===1,1,With[{m=primeMS[n]},If[Length[m]===1,leafcount[First[m]],Total[leafcount/@m]]]];
Select[Range[nn],UnsameQ@@leafcount/@primeMS[#]&]

cp's OEIS Frontend

A317711 Numbers that are not uniform tree numbers.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A301344 Regular triangle where T(n,k) is the number of semi-binary rooted trees with n nodes and k leaves.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A298424 Matula-Goebel numbers of rooted trees in which all positive outdegrees are the same.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A318230 Number of inequivalent leaf-colorings of binary rooted trees with 2n + 1 nodes.

Views

Author

Keywords

Examples

Links

Crossrefs

Programs

PARI

Extensions

A358375 Numbers k such that the k-th standard ordered rooted tree is binary.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A245824 Triangle read by rows: row n>=1 contains in increasing order the Matula numbers of the rooted binary trees with n leaves.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

Extensions

A303024 Matula-Goebel numbers of anti-binary (no binary branchings) rooted trees.

Views

Author

Keywords

Examples

Crossrefs

Programs

Mathematica

A318612 Matula-Goebel numbers of powerful rooted trees.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A298305 Matula-Goebel numbers of rooted trees with strictly thinning limbs.

Views

Author

Keywords