A358507 -id:A358507 - cp's OEIS frontend

A206487 Number of ordered trees isomorphic (as rooted trees) to the rooted tree having Matula number n.

1, 1, 1, 1, 1, 2, 1, 1, 1, 2, 1, 3, 2, 2, 2, 1, 1, 3, 1, 3, 2, 2, 1, 4, 1, 4, 1, 3, 2, 6, 1, 1, 2, 2, 2, 6, 3, 2, 4, 4, 2, 6, 2, 3, 3, 2, 2, 5, 1, 3, 2, 6, 1, 4, 2, 4, 2, 4, 1, 12, 3, 2, 3, 1, 4, 6, 1, 3, 2, 6, 3, 10, 2, 6, 3, 3, 2, 12, 2, 5, 1, 4, 1, 12, 2, 4, 4, 4, 4, 12, 4, 3, 2, 4, 2, 6, 1, 3, 3, 6, 4, 6, 1, 8, 6, 2, 3, 10, 2, 6, 6, 5, 6, 6, 2, 6, 6, 2, 2, 20, 1, 6, 4, 3, 1, 12, 1, 1, 4, 12, 1, 12, 2, 2, 4, 4, 2, 6, 2, 12, 4, 6, 4, 15, 4, 4, 3, 9, 2, 12, 6, 4, 3, 6, 2, 24, 3, 4, 2, 6

Offset: 1

Emeric Deutsch, Apr 14 2012

nonn

The Matula-Goebel number of a rooted tree is 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.

a(n) = the number of times n occurs in A127301. - Antti Karttunen, Jan 03 2013

			a(4)=1 because the rooted tree with Matula number 4 is V and there is no other ordered tree isomorphic to V. a(6)=2 because the rooted tree corresponding to n = 6 is obtained by joining the trees A - B and C - D - E at their roots A and C. Interchanging their order, we obtain another ordered tree, isomorphic (as rooted tree) to the first one.

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
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. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
P. Schultz, Enumeration of rooted trees with an application to group presentations, Discrete Math., 41, 1982, 199-214.
Index entries for sequences related to Matula-Goebel numbers

Cf. A127301.
Positions of 1's are 1 and A214577.
Positions of first appearances are A358507, unsorted A358508.
A000108 counts ordered rooted trees, unordered A000081.
A061775 and A196050 count nodes and edges in Matula-Goebel trees.
Cf. A001263, A003238, A014486, A358506.

with(numtheory): F := proc (n) options operator, arrow: factorset(n) end proc: PD := proc (n) local k, m, j: for k to nops(F(n)) do m[k] := 0: for j while is(n/F(n)[k]^j, integer) = true do m[k] := m[k]+1 end do end do: [seq([F(n)[q], m[q]], q = 1 .. nops(F(n)))] end proc: a := proc (n) if n = 1 then 1 elif bigomega(n) = 1 then a(pi(n)) else mul(a(PD(n)[j][1])^PD(n)[j][2], j = 1 .. nops(F(n)))*factorial(add(PD(n)[k][2], k = 1 .. nops(F(n))))/mul(factorial(PD(n)[k][2]), k = 1 .. nops(F(n))) end if end proc: seq(a(n), n = 1 .. 160);

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]
MGTree[n_Integer]:=If[n===1,{},MGTree/@primeMS[n]]
treeperms[t_]:=Times@@Cases[t,b:{}:>Length[Permutations[b]],{0,Infinity}];
Table[treeperms[MGTree[n]],{n,100}] (* Gus Wiseman, Nov 21 2022 *)

a(1)=1; denoting by p(t) the t-th prime, if n = p(n_1)^{k_1}...p(n_r)^{k_r}, then a(n) = a(n_1)^{k_1}...a(n_r)^{k_r}*(k_1 + ... + k_r)!/[(k_1)!...(k_r)!] (see Theorem 1 in the Schultz reference, where the exponents k_j of N(n_j) have been inadvertently omitted).

A358506 Matula-Goebel number of the n-th standard ordered rooted tree.

Original entry on oeis.org

1, 2, 3, 4, 5, 6, 6, 8, 7, 10, 9, 12, 10, 12, 12, 16, 11, 14, 15, 20, 15, 18, 18, 24, 14, 20, 18, 24, 20, 24, 24, 32, 13, 22, 21, 28, 25, 30, 30, 40, 21, 30, 27, 36, 30, 36, 36, 48, 22, 28, 30, 40, 30, 36, 36, 48, 28, 40, 36, 48, 40, 48, 48, 64, 13, 26, 33, 44

Offset: 1

Gus Wiseman, Nov 20 2022

nonn

First differs from A333219 at a(65) = 13, A333219(65) = 17.
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.
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 first eight standard ordered trees are: o, (o), ((o)), (oo), (((o))), ((o)o), (o(o)), (ooo), with Matula-Goebel numbers: 1, 2, 3, 4, 5, 6, 6, 8.

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

For binary instead of standard encoding we have A127301.
There are exactly A206487(n) appearances of n.
For binary instead of Matula-Goebel encoding we have A358505.
Positions of first appearances are A358522, sorted A358521.
A000108 counts ordered rooted trees, unordered A000081.
A214577 and A358377 rank trees with no permutations.
Cf. A001263, A014486, A061775, A196050, A358371, A358372, A358378, A358379, A358507, A358508.

stc[n_]:=Differences[Prepend[Join @@ Position[Reverse[IntegerDigits[n,2]],1],0]]//Reverse;
srt[n_]:=If[n==1,{},srt/@stc[n-1]];
mgnum[t_]:=If[t=={},1,Times@@Prime/@mgnum/@t];
Table[mgnum[srt[n]],{n,100}]

A358508 Least Matula-Goebel number of a tree with exactly n permutations.

Original entry on oeis.org

1, 6, 12, 24, 48, 30, 192, 104, 148, 72, 3072, 60, 12288, 832, 144, 712, 196608, 222, 786432, 120, 288, 13312

Offset: 1

Gus Wiseman, Nov 20 2022

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.

To get a permutation of a tree, we choose a permutation of the multiset of branches of each node.

			The terms together with their corresponding trees begin:
      1: o
      6: (o(o))
     12: (oo(o))
     24: (ooo(o))
     48: (oooo(o))
     30: (o(o)((o)))
    192: (oooooo(o))
    104: (ooo(o(o)))
    148: (oo(oo(o)))
     72: (ooo(o)(o))
   3072: (oooooooooo(o))
     60: (oo(o)((o)))
  12288: (oooooooooooo(o))
    832: (oooooo(o(o)))
    144: (oooo(o)(o))
    712: (ooo(ooo(o)))

Position of first appearance of n in A206487.
The sorted version is A358507.
A000081 counts rooted trees, ordered A000108.
A214577 and A358377 rank trees with no permutations.
Cf. A001263, A032027, A061775, A127301, A196050, A358378, A358506, A358521, A358522.

primeMS[n_]:=If[n===1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]]
MGTree[n_Integer]:=If[n===1,{},MGTree/@primeMS[n]]
treeperms[t_]:=Times @@ Cases[t,b:{}:>Length[Permutations[b]],{0,Infinity}];
uv=Table[treeperms[MGTree[n]],{n,100000}];
Table[Position[uv,k][[1,1]],{k,Min@@Complement[Range[Max@@uv],uv]-1}]

A358525 Number of distinct permutations of the n-th composition in standard order.

Original entry on oeis.org

1, 1, 1, 1, 1, 2, 2, 1, 1, 2, 1, 3, 2, 3, 3, 1, 1, 2, 2, 3, 2, 3, 3, 4, 2, 3, 3, 4, 3, 4, 4, 1, 1, 2, 2, 3, 1, 6, 6, 4, 2, 6, 1, 6, 6, 6, 6, 5, 2, 3, 6, 4, 6, 6, 6, 5, 3, 4, 6, 5, 4, 5, 5, 1, 1, 2, 2, 3, 2, 6, 6, 4, 2, 3, 3, 12, 3, 12, 12, 5, 2, 6, 3, 12, 3, 4

Offset: 0

Gus Wiseman, Nov 21 2022

nonn

The k-th composition in standard order (graded reverse-lexicographic, A066099) is obtained by taking the set of positions of 1's in the reversed binary expansion of k, prepending 0, taking first differences, and reversing again. This gives a bijective correspondence between nonnegative integers and integer compositions.

			The a(45) = 6 permutations are: (2121), (2112), (2211), (1221), (1212), (1122).

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

See link for sequences related to standard compositions.
Positions of 1's are A272919.
Cf. A000120, A048896, A070939, A329395, A333766, A358371, A358372, A358379, A358505, A358507, A358508.

stc[n_]:=Reverse[Differences[Prepend[Join@@Position[Reverse[IntegerDigits[n,2]],1],0]]];
Table[Length[Permutations[stc[n]]],{n,0,100}]

cp's OEIS Frontend

A206487 Number of ordered trees isomorphic (as rooted trees) to the rooted tree having Matula number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A358506 Matula-Goebel number of the n-th standard ordered rooted tree.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A358508 Least Matula-Goebel number of a tree with exactly n permutations.

Views

Author

Keywords

Comments

Examples

Crossrefs

Programs

Mathematica

A358525 Number of distinct permutations of the n-th composition in standard order.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica