A061773 -id:A061773 - cp's OEIS frontend

A347539 Matula-Goebel number of the n-th tree in Beyer and Hedetniemi's rooted tree iteration (A346913).

1, 2, 3, 4, 5, 7, 6, 8, 11, 17, 13, 10, 19, 14, 9, 12, 16, 31, 59, 41, 29, 22, 67, 43, 34, 23, 37, 26, 15, 20, 53, 38, 21, 28, 18, 24, 32, 127, 277, 179, 109, 79, 62, 331, 191, 139, 118, 83, 157, 101, 82, 47, 71, 58, 33, 44, 241, 163, 134, 73, 107, 86, 51, 68

Offset: 1

Kevin Ryde, Sep 06 2021

nonn

This sequence is a permutation of the natural numbers, with inverse A347540.

			For n=33, row 33 of A346913 is levels sequence 1,2,3,3,2,3 which is the following tree,
  root      21          a(33) = 21 Matula-Goebel number
            |  \        (being prime(4)*prime(2) = 21)
  children  4    2
            |\   |
            1 1  1

Kevin Ryde, Table of n, a(n) for n = 1..7813 (trees <= 12 vertices)
Index entries for sequences that are permutations of the natural numbers

Cf. A346913, A347540 (inverse), A061773, A127301.

A214572 The Matula-Goebel numbers of the rooted trees having 8 vertices.

Original entry on oeis.org

45, 50, 54, 55, 60, 63, 65, 66, 69, 70, 72, 77, 78, 80, 84, 85, 87, 88, 91, 92, 93, 94, 95, 96, 97, 98, 102, 103, 104, 111, 112, 113, 114, 116, 119, 122, 123, 124, 128, 129, 133, 136, 137, 142, 146, 148, 149, 151, 152, 158, 159, 164, 166, 167, 172, 173, 177, 178, 181, 193, 199, 201, 202, 211, 212, 214, 218, 223, 227, 233, 236, 239, 254, 262, 263, 268, 269, 271, 278, 283, 293, 311, 314, 326, 337, 353, 358, 367, 373, 382, 383, 401, 421, 431, 443, 461, 482, 547, 554, 577, 587, 599, 647, 662, 709, 739, 757, 797, 919, 967, 1063, 1153, 1523, 1787, 2221

Offset: 1

Emeric Deutsch, Aug 14 2012

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.

It is a finite sequence; number of entries is 115 = A000081(8).

			128=2^7 is in the sequence; it is the Matula-Goebel number of the star K_{1,7}.

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
E. 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. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Index entries for sequences related to Matula-Goebel numbers

Cf. A005517, A005518, A061775, A000081.

Row n=8 of A061773. - Alois P. Heinz, Sep 06 2012

with(numtheory): N := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 1 elif bigomega(n) = 1 then 1+N(pi(n)) else N(r(n))+N(s(n))-1 end if end proc: A := {}: for n to 3000 do if N(n) = 8 then A := `union`(A, {n}) else  end if end do: A;

MGweight[n_] := If[n == 1, 1, 1 + Total[Cases[FactorInteger[n], {p_, k_} :> k*MGweight[PrimePi[p]]]]];
Select[Range[Nest[Prime, 8, 4]], MGweight[#] == 8&] (* Jean-François Alcover, Nov 11 2017, after Gus Wiseman's program for A061773 *)

A061775(n) yields the number of vertices of the rooted tree with Matula-Goebel number n. We use it to find the Matula-Goebel numbers of the rooted trees having 8 vertices.

A318048 Size of the span of the unlabeled rooted tree with Matula-Goebel number n.

Original entry on oeis.org

1, 2, 3, 2, 4, 4, 4, 2, 6, 6, 5, 4, 6, 3, 9, 2, 6, 6, 4, 6, 6, 8, 10, 4, 12, 6, 10, 4, 9, 9, 6, 2, 12, 6, 9, 6, 6, 4, 9, 6, 9, 7, 6, 8, 15, 10, 15, 4, 5, 12, 9, 7, 4, 10, 16, 4, 7, 9, 8, 9, 10, 10, 11, 2, 13, 12, 6, 7, 14, 10, 9, 6, 10, 7, 21, 3, 12, 10, 12, 6

Offset: 1

Gus Wiseman, Aug 13 2018

nonn

The span of a tree is defined to be the set of possible terminal subtrees of initial subtrees, or, which is the same, the set of possible initial subtrees of terminal subtrees.

			42 is the Matula-Goebel number of (o(o)(oo)), which has span {o, (o), (oo), (ooo), (oo(oo)), (o(o)o), (o(o)(oo))}, so a(42) = 7.

Index entries for sequences related to Matula-Goebel numbers

Cf. A000081, A007097, A007853, A049076, A061773, A061775, A109082, A109129, A206491, A317713, A318046.

ext[c_,{}]:=c;ext[c_,s:{}]:=Extract[c,s];rpp[c_,v_,{}]:=v;rpp[c_,v_,s:{}]:=ReplacePart[c,v,s];
RLO[ear_,rue:{}]:=Union@@(Function[x,rpp[ear,x,#2]]/@ReplaceList[ext[ear,#2],#1]&@@@Select[Tuples[{rue,Position[ear,_]}],MatchQ[ext[ear,#[[2]]],#[[1,1]]]&]);
RL[ear_,rue:{}]:=FixedPoint[Function[keeps,Union[keeps,Join@@(RLO[#,rue]&/@keeps)]],{ear}];
primeMS[n_]:=If[n==1,{},Flatten[Cases[FactorInteger[n],{p_,k_}:>Table[PrimePi[p],{k}]]]];
MGTree[n_]:=If[n==1,{},MGTree/@primeMS[n]];
Table[Length[Union[Cases[RL[MGTree[n],{List[__List]:>List[]}],_List,{1,Infinity}]]],{n,100}]

A214565 Sum(M(t)), where summation is over all rooted trees t with n vertices and M(t) is the number of ways to take apart t by sequentially removing terminal edges (see A206494).

Original entry on oeis.org

1, 1, 3, 12, 66, 426, 3392, 30412, 314994, 3622332, 46379994, 648971940, 9923253672, 163720448184, 2910558776412, 55341456735744

Offset: 1

Emeric Deutsch, Jul 21 2012

			a(4) = 12 because there are four rooted trees with 4 vertices; their Matula-Goebel numbers are 5,6,7, and 8 and, consequently M(5)+M(6)+M(7)+M(8) = 1+3+2+6 = 12 (see A206494).

J. Fulman, Mixing time for a random walk on rooted trees, The Electronic J. of Combinatorics, 16, 2009, R139.
M. E. Hoffman, Combinatorics of rooted trees and Hopf algebras, Trans. Amer. Math. Soc., 355, 2003, 3795-3811.

Cf. A206494, A061773.

Apparently, no formula is available. The example gives a hint how the first ten terms of the sequence have been computed (using Maple).

a(11)-a(16) from Alois P. Heinz, Sep 08 2012

cp's OEIS Frontend

A347539 Matula-Goebel number of the n-th tree in Beyer and Hedetniemi's rooted tree iteration (A346913).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

A214572 The Matula-Goebel numbers of the rooted trees having 8 vertices.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

Formula

A318048 Size of the span of the unlabeled rooted tree with Matula-Goebel number n.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Mathematica

A214565 Sum(M(t)), where summation is over all rooted trees t with n vertices and M(t) is the number of ways to take apart t by sequentially removing terminal edges (see A206494).

Views

Author

Keywords

Examples

Links

Crossrefs

Formula

Extensions