A324923 -id:A324923 - cp's OEIS frontend

A324935 Matula-Goebel numbers of rooted trees whose non-leaf terminal subtrees are all different.

1, 2, 3, 4, 5, 6, 7, 8, 10, 11, 12, 13, 14, 16, 17, 19, 20, 21, 22, 24, 26, 28, 29, 31, 32, 34, 35, 37, 38, 40, 41, 42, 43, 44, 48, 51, 52, 53, 56, 57, 58, 59, 62, 64, 67, 68, 70, 71, 73, 74, 76, 77, 79, 80, 82, 84, 85, 86, 88, 89, 91, 95, 96, 101, 102, 104

Offset: 1

Gus Wiseman, Mar 21 2019

nonn

Every positive integer has a unique factorization into factors q(i) = prime(i)/i, i > 0. This sequence consists of all numbers where this factorization has all distinct factors, except possibly for any multiplicity of q(1). For example, 22 = q(1)^2 q(2) q(3) q(5) is in the sequence, while 50 = q(1)^3 q(2)^2 q(3)^2 is not.

The enumeration of these trees by number of vertices is A324936.

			The sequence of trees together with their Matula-Goebel numbers begins:
   1: o
   2: (o)
   3: ((o))
   4: (oo)
   5: (((o)))
   6: (o(o))
   7: ((oo))
   8: (ooo)
  10: (o((o)))
  11: ((((o))))
  12: (oo(o))
  13: ((o(o)))
  14: (o(oo))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  20: (oo((o)))
  21: ((o)(oo))
  22: (o(((o))))
  24: (ooo(o))
  26: (o(o(o)))
  28: (oo(oo))
  29: ((o((o))))
  31: (((((o)))))

Gus Wiseman, The first 36 rooted trees whose non-leaf terminal subtrees are all different, together with their Matula-Goebel numbers.

Cf. A000081, A004111, A007097, A061775, A196050, A276625, A290822, A317713.

Cf. A324850, A324922, A324923, A324924, A324931, A324934, A324936.

difac[n_]:=If[n==1,{},With[{i=PrimePi[FactorInteger[n][[1,1]]]},Sort[Prepend[difac[n*i/Prime[i]],i]]]];
Select[Range[100],UnsameQ@@DeleteCases[difac[#],1]&]

A324934 Inverse permutation to A324931.

Original entry on oeis.org

1, 2, 4, 3, 10, 6, 9, 5, 12, 15, 35, 8, 24, 14, 26, 7, 41, 17, 23, 20, 25, 47, 52, 13, 58, 34, 28, 19, 79, 37, 184, 11, 87, 61, 53, 22, 56, 33, 60, 30, 145, 36, 92, 70, 65, 75, 164, 18, 51, 82, 98, 46, 54, 39, 178, 29, 59, 106, 293, 49, 122, 245, 63, 16, 125

Offset: 1

Gus Wiseman, Mar 21 2019

nonn

Cf. A003963, A120383, A196050, A317713, A324846, A324849, A324850, A324922, A324923, A324924, A324925, A324931.

A358729 Difference between the number of nodes and the node-height of the rooted tree with Matula-Goebel number n.

Original entry on oeis.org

0, 0, 0, 1, 0, 1, 1, 2, 2, 1, 0, 2, 1, 2, 2, 3, 1, 3, 2, 2, 3, 1, 2, 3, 3, 2, 4, 3, 1, 3, 0, 4, 2, 2, 3, 4, 2, 3, 3, 3, 1, 4, 2, 2, 4, 3, 2, 4, 4, 4, 3, 3, 3, 5, 3, 4, 4, 2, 1, 4, 3, 1, 5, 5, 4, 3, 2, 3, 4, 4, 2, 5, 3, 3, 5, 4, 3, 4, 1, 4, 6, 2, 2, 5, 4, 3, 3, 3, 3, 5, 4, 4, 2, 3, 4, 5, 3, 5, 4, 5, 2, 4, 4, 4, 5, 4, 3, 6

Offset: 1

Gus Wiseman, Nov 29 2022

nonn

Node-height is the number of nodes in the longest path from root to 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.
Because the number of distinct terminal subtrees of the rooted tree with Matula-Goebel number n, i.e., A317713(n) (= 1+A324923(n)), is always at least one larger than the depth of the same tree (= A109082(n)), it follows that a(n) >= A366386(n) for all n. - Antti Karttunen, Oct 23 2023

			The tree (oo(oo(o))) with Matula-Goebel number 148 has 8 nodes and node-height 4, so a(148) = 4.

Antti Karttunen, Table of n, a(n) for n = 1..100000
Index entries for sequences related to Matula-Goebel numbers

Positions of 0's are A007097.
Positions of first appearances are A358730.
Positions of 1's are A358731.
Other differences: A358580, A358724, A358726.
A000081 counts rooted trees, ordered A000108.
A034781 counts rooted trees by nodes and height, ordered A080936.
A055277 counts rooted trees by nodes and leaves, ordered A001263.
MG statistics: A061775, A109082, A109129, A196050, A342507, A358552.
MG core: A000040, A000720, A001222, A056239, A112798.
Cf. A206487, A209638, A316321, A358576, A358577, A358592, A358725, A366386.

MGTree[n_]:=If[n==1,{},MGTree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Table[Count[MGTree[n],_,{0,Infinity}]-(Depth[MGTree[n]]-1),{n,100}]

A061775(n) = if(1==n, 1, if(isprime(n), 1+A061775(primepi(n)), {my(pfs,t,i); pfs=factor(n); pfs[,1]=apply(t->A061775(t),pfs[,1]); (1-bigomega(n)) + sum(i=1, omega(n), pfs[i,1]*pfs[i,2])}));
A358552(n) = { my(v=factor(n)[, 1], d=0); while(#v, d++; v=fold(setunion, apply(p->factor(primepi(p))[, 1]~, v))); (1+d); }; \\ (after program given in A109082 by Kevin Ryde, Sep 21 2020)
A358729(n) = (A061775(n)-A358552(n)); \\ Antti Karttunen, Oct 23 2023

a(n) = A061775(n) - A358552(n).

a(n) = A196050(n) - A109082(n). - Antti Karttunen, Oct 23 2023

Data section extended up to a(108) by Antti Karttunen, Oct 23 2023

A324936 Number of unlabeled rooted trees with n vertices whose non-leaf terminal subtrees are all different.

Original entry on oeis.org

1, 1, 2, 4, 8, 17, 37, 83, 189, 436, 1014, 2373, 5578, 13156, 31104, 73665, 174665, 414427, 983606, 2334488

Offset: 1

Gus Wiseman, Mar 21 2019

The Matula-Goebel numbers of these trees are given by A324935.

			The a(1) = 1 through a(6) = 17 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)))
                                     ((oo(o)))
                                     (o((oo)))
                                     (o(o(o)))
                                     (oo((o)))
                                     ((((oo))))
                                     (((o(o))))
                                     ((o((o))))
                                     (o(((o))))
                                     (((((o)))))

Cf. A000081, A004111, A290689, A317713, A324850, A324922, A324923, A324924, A324931, A324935.

durt[n_]:=Join@@Table[Select[Union[Sort/@Tuples[durt/@ptn]],UnsameQ@@Cases[#,{},{0,Infinity}]&],{ptn,IntegerPartitions[n-1]}];
Table[Length[durt[n]],{n,10}]

A325614 Unsorted q-signature of n.

Original entry on oeis.org

1, 1, 1, 2, 1, 1, 1, 2, 1, 2, 1, 3, 2, 2, 2, 1, 1, 1, 1, 1, 1, 3, 1, 2, 1, 1, 3, 1, 2, 2, 1, 4, 2, 1, 1, 3, 2, 3, 1, 3, 1, 1, 3, 1, 1, 2, 1, 1, 1, 2, 2, 1, 4, 1, 2, 2, 2, 3, 1, 1, 3, 3, 4, 1, 2, 1, 1, 1, 3, 2, 1, 1, 1, 1, 1, 1, 5, 2, 2, 1, 1, 3, 1, 1, 3, 1, 1

Offset: 1

Gus Wiseman, May 12 2019

Every positive integer has a unique q-factorization (encoded by A324924) into factors q(i) = prime(i)/i, i > 0. For example:
   11 = q(1) q(2) q(3) q(5)
   50 = q(1)^3 q(2)^2 q(3)^2
  360 = q(1)^6 q(2)^3 q(3)
Row n lists the nonzero multiplicities in the q-factorization of n, in order of q-index. For example, row 11 is (1,1,1,1) and row 360 is (6,3,1).

			Triangle begins:
  {}
  1
  1 1
  2
  1 1 1
  2 1
  2 1
  3
  2 2
  2 1 1
  1 1 1 1
  3 1
  2 1 1
  3 1
  2 2 1
  4
  2 1 1
  3 2
  3 1
  3 1 1

Row lengths are A324923.
Row sums are A196050.
Row-maxima are A109129.
Cf. A118914, A324922, A324924, A324931, A324934, A325608, A325609, A325613, A325615, A325660.

difac[n_]:=If[n==1,{},With[{i=PrimePi[FactorInteger[n][[1,1]]]},Sort[Prepend[difac[n*i/Prime[i]],i]]]];
Table[Length/@Split[difac[n]],{n,30}]

A325660 Number of ones in the q-signature of n.

Original entry on oeis.org

0, 1, 2, 0, 3, 1, 1, 0, 0, 2, 4, 1, 2, 1, 1, 0, 2, 0, 1, 2, 2, 3, 1, 1, 0, 2, 0, 1, 3, 1, 5, 0, 2, 2, 3, 0, 2, 1, 1, 2, 3, 2, 2, 3, 1, 1, 2, 1, 0, 0, 3, 2, 1, 0, 1, 1, 2, 3, 3, 1, 1, 4, 1, 0, 2, 2, 2, 2, 1, 3, 3, 0, 3, 2, 0, 1, 4, 1, 4, 2, 0, 3, 2, 2, 4, 2, 2

Offset: 1

Gus Wiseman, May 13 2019

nonn

Every positive integer has a unique q-factorization (encoded by A324924) into factors q(i) = prime(i)/i, i > 0. For example:
   11 = q(1) q(2) q(3) q(5)
   50 = q(1)^3 q(2)^2 q(3)^2
  360 = q(1)^6 q(2)^3 q(3)
Then a(n) is the number of factors of multiplicity one in the q-factorization of n.
Also the number of rooted trees appearing only once in the multiset of terminal subtrees of the rooted tree with Matula-Goebel number n.

Cf. A001694, A055231, A056169, A056239, A112798, A118914, A124010.
Matula-Goebel numbers: A007097, A061775, A109129, A196050, A317713, A324968.
q-factorization: A324922, A324923, A324924, A325614, A325661.

difac[n_]:=If[n==1,{},With[{i=PrimePi[FactorInteger[n][[1,1]]]},Sort[Prepend[difac[n*i/Prime[i]],i]]]];
Table[Count[Length/@Split[difac[n]],1],{n,100}]

A324968 Matula-Goebel numbers of rooted identity trees whose non-leaf terminal subtrees are all different.

Original entry on oeis.org

1, 2, 3, 5, 6, 10, 11, 13, 22, 26, 29, 31, 41, 58, 62, 79, 82, 101, 109, 127, 158, 179, 202, 218, 254, 271, 293, 358, 401, 421, 542, 547, 586, 599, 709, 802, 842, 929, 1063, 1094, 1198, 1231, 1361, 1418, 1609, 1741, 1858, 1913, 2126, 2411, 2462, 2722, 2749

Offset: 1

Gus Wiseman, Mar 21 2019

nonn

A rooted identity tree is an unlabeled rooted tree with no repeated branches directly under the same root. This sequence ranks rooted identity trees satisfying the additional condition that all non-leaf terminal subtrees are different.

			The sequence of trees together with the Matula-Goebel numbers begins:
    1: o
    2: (o)
    3: ((o))
    5: (((o)))
    6: (o(o))
   10: (o((o)))
   11: ((((o))))
   13: ((o(o)))
   22: (o(((o))))
   26: (o(o(o)))
   29: ((o((o))))
   31: (((((o)))))
   41: (((o(o))))
   58: (o(o((o))))
   62: (o((((o)))))
   79: ((o(((o)))))
   82: (o((o(o))))
  101: ((o(o(o))))
  109: (((o((o)))))
  127: ((((((o))))))

Gus Wiseman, The first 36 trees together with their Matula-Goebel numbers.

Cf. A000081, A004111, A007097, A196050, A276625, A317713, A324850, A324923, A324935, A324936, A324969, A324970, A324978.

mgtree[n_Integer]:=If[n==1,{},mgtree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],And[And@@Cases[mgtree[#],q:{}:>UnsameQ@@q,{0,Infinity}],UnsameQ@@Cases[mgtree[#],{},{0,Infinity}]]&]

Intersection of A324935 and A276625.

A324970 Matula-Goebel numbers of rooted identity trees where not all terminal subtrees are different.

Original entry on oeis.org

15, 30, 33, 39, 47, 55, 65, 66, 78, 87, 93, 94, 110, 113, 123, 130, 137, 141, 143, 145, 155, 165, 167, 174, 186, 195, 205, 211, 226, 235, 237, 246, 257, 274, 282, 286, 290, 303, 310, 313, 317, 319, 327, 330, 334, 339, 341, 377, 381, 390, 395, 397, 403, 410

Offset: 1

Gus Wiseman, Mar 21 2019

nonn

A rooted identity tree is an unlabeled rooted tree with no repeated branches directly under the same root.

			The sequence of trees together with the Matula-Goebel numbers begins:
   15: ((o)((o)))
   30: (o(o)((o)))
   33: ((o)(((o))))
   39: ((o)(o(o)))
   47: (((o)((o))))
   55: (((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))))
  110: (o((o))(((o))))
  113: ((o(o)((o))))
  123: ((o)((o(o))))
  130: (o((o))(o(o)))
  137: (((o)(((o)))))
  141: ((o)((o)((o))))
  143: ((((o)))(o(o)))
  145: (((o))(o((o))))
  155: (((o))((((o)))))
  165: ((o)((o))(((o))))
  167: (((o)(o(o))))
  174: (o(o)(o((o))))
  186: (o(o)((((o)))))
  195: ((o)((o))(o(o)))

Gus Wiseman, The first 36 trees together with their Matula-Goebel numbers.

Cf. A000081, A004111, A007097, A196050, A276625, A317713, A324850, A324923, A324935, A324936, A324968, A324971, A324978.

mgtree[n_Integer]:=If[n==1,{},mgtree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],And[And@@Cases[mgtree[#],q:{}:>UnsameQ@@q,{0,Infinity}],!UnsameQ@@Cases[mgtree[#],{},{0,Infinity}]]&]

Complement of A324935 in A276625.

A324971 Number of rooted identity trees with n vertices whose non-leaf terminal subtrees are not all different.

Original entry on oeis.org

0, 0, 0, 0, 0, 1, 4, 12, 31, 79, 192, 459, 1082, 2537, 5922, 13816, 32222, 75254, 176034, 412667, 969531, 2283278

Offset: 1

Gus Wiseman, Mar 21 2019

A rooted identity tree is an unlabeled rooted tree with no repeated branches directly under the same root.

			The a(6) = 1 through a(8) = 12 trees:
  ((o)((o)))  ((o)(o(o)))   (o(o)(o(o)))
              (o(o)((o)))   (((o))(o(o)))
              (((o)((o))))  (((o)(o(o))))
              ((o)(((o))))  ((o)((o(o))))
                            ((o)(o((o))))
                            ((o(o)((o))))
                            (o((o)((o))))
                            (o(o)(((o))))
                            ((((o)((o)))))
                            (((o))(((o))))
                            (((o)(((o)))))
                            ((o)((((o)))))

The Matula-Goebel numbers of these trees are given by A324970.

Cf. A000081, A004111, A290689, A317713, A324850, A324922, A324923, A324924, A324931, A324935, A324936, A324979.

rits[n_]:=Join@@Table[Select[Union[Sort/@Tuples[rits/@ptn]],UnsameQ@@#&],{ptn,IntegerPartitions[n-1]}];
Table[Length[Select[rits[n],!UnsameQ@@Cases[#,{},{0,Infinity}]&]],{n,10}]

A324978 Matula-Goebel numbers of rooted trees that are not identity trees but whose non-leaf terminal subtrees are all different.

Original entry on oeis.org

4, 7, 8, 12, 14, 16, 17, 19, 20, 21, 24, 28, 32, 34, 35, 37, 38, 40, 42, 43, 44, 48, 51, 52, 53, 56, 57, 59, 64, 67, 68, 70, 71, 73, 74, 76, 77, 80, 84, 85, 86, 88, 89, 91, 95, 96, 102, 104, 106, 107, 112, 114, 116, 118, 124, 128, 129, 131, 133, 134, 136, 139

Offset: 1

Gus Wiseman, Mar 21 2019

nonn

An unlabeled rooted tree is an identity tree if there are no repeated branches directly under the same root.

			The sequence of trees together with the Matula-Goebel numbers begins:
   4: (oo)
   7: ((oo))
   8: (ooo)
  12: (oo(o))
  14: (o(oo))
  16: (oooo)
  17: (((oo)))
  19: ((ooo))
  20: (oo((o)))
  21: ((o)(oo))
  24: (ooo(o))
  28: (oo(oo))
  32: (ooooo)
  34: (o((oo)))
  35: (((o))(oo))
  37: ((oo(o)))
  38: (o(ooo))
  40: (ooo((o)))
  42: (o(o)(oo))
  43: ((o(oo)))

Gus Wiseman, The first 36 trees together with their Matula-Goebel numbers.

Cf. A000081, A004111, A007097, A196050, A276625, A317713, A324850, A324923, A324935, A324936, A324968, A324969, A324970, A324971, A324979.

mgtree[n_]:=If[n==1,{},mgtree/@Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
Select[Range[100],And[!And@@Cases[mgtree[#],q:{}:>UnsameQ@@q,{0,Infinity}],UnsameQ@@Cases[mgtree[#],{},{0,Infinity}]]&]

Complement of A276625 in A324935.

cp's OEIS Frontend

A324935 Matula-Goebel numbers of rooted trees whose non-leaf terminal subtrees are all different.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A324934 Inverse permutation to A324931.

Views

Author

Keywords

Crossrefs

A358729 Difference between the number of nodes and the node-height of the rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

PARI

Formula

Extensions

A324936 Number of unlabeled rooted trees with n vertices whose non-leaf terminal subtrees are all different.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325614 Unsorted q-signature of n.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A325660 Number of ones in the q-signature of n.

Views

Author

Keywords

Comments

Crossrefs

Programs

Mathematica

A324968 Matula-Goebel numbers of rooted identity trees whose non-leaf terminal subtrees are all different.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A324970 Matula-Goebel numbers of rooted identity trees where not all terminal subtrees are different.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

Formula

A324971 Number of rooted identity trees with n vertices whose non-leaf terminal subtrees are not all different.

Views

Author