login
This site is supported by donations to The OEIS Foundation.

 

Logo

Annual Appeal: Please make a donation to keep the OEIS running. In 2018 we replaced the server with a faster one, added 20000 new sequences, and reached 7000 citations (often saying "discovered thanks to the OEIS").
Other ways to donate

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A061773 Triangle in which n-th row lists Matula-Goebel numbers for all rooted trees with n nodes. 29
1, 2, 3, 4, 5, 6, 7, 8, 9, 10, 11, 12, 13, 14, 16, 17, 19, 15, 18, 20, 21, 22, 23, 24, 26, 28, 29, 31, 32, 34, 37, 38, 41, 43, 53, 59, 67, 25, 27, 30, 33, 35, 36, 39, 40, 42, 44, 46, 47, 48, 49, 51, 52, 56, 57, 58, 61, 62, 64, 68, 71, 73, 74, 76, 79, 82, 83, 86, 89, 101, 106 (list; graph; refs; listen; history; text; internal format)
OFFSET

1,2

COMMENTS

Let p(1)=2, ... denote the primes. The label f(T) for a rooted tree T is 1 if T has 1 node, otherwise f(T) = Product p(f(T_i)) where the T_i are the subtrees obtained by deleting the root and the edges adjacent to it.

n-th row has A000081(n) terms.

First entry in row n is A005517(n).

Last entry in row n is A005518(n).

The Maple program yields row n after defining F = A005517(n) and L = A005518(n).

LINKS

Alois P. Heinz, Rows n = 1..12, flattened

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.

D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.

Gus Wiseman, Matula-Goebel trees triangle illustration n=1..6

Index entries for sequences related to Matula-Goebel numbers

Index entries for sequences related to rooted trees

Index entries for sequences related to trees

EXAMPLE

The labels for the rooted trees with at most 4 nodes are as follows (x is the root):

                                         o

                                         |

               o         o        o   o  o

               |          \        \ /   |

     o  o   o  o  o o o    o   o    o    o

     |   \ /   |   \|/      \ /     |    |

  x  x    x    x    x        x      x    x

  1  2    4    3    8        6      7    5 (label)

Triangle begins:

1;

2;

3,4;

5,6,7,8;

9,10,11,12,13,14,16,17,19;

15,18,20,21,22,23,24,26,28,29,31,32,34,37,38,41,43,53,59,67;

25,27,30,33,35,36,39,40,42,44,46,47,48,49,51,52,56,57,58,61,62,64,68,\

71,73,74,76,79,82,83,86,89,101,106,107,109,118,127,131,134,139,157,163,\

179,191,241,277,331;

...

Triangle of rooted trees represented as finitary multisets begins:

(),

(()),

((())), (()()),

(((()))), (()(())), ((()())), (()()()),

((())(())), (()((()))), ((((())))), (()()(())), ((()(()))), (()(()())), (()()()()), (((()()))), ((()()())). - Gus Wiseman, Dec 21 2016

MAPLE

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

MATHEMATICA

F[n_] := F[n] = Which[n == 1, 1, n == 2, 2, Mod[n, 3] == 0, 3*5^(n/3-1), Mod[n, 3] == 1, 5^(n/3-1/3), True, 9*5^(n/3-5/3)]; L[n_] := L[n] = Switch[n, 1, 1, 2, 2, 3, 4, 4, 8, _, Prime[L[n-1]]]; r[m_] := FactorInteger[m][[1, 1]]; s[m_] := m/r[m]; NN[m_] := NN[m] = Which[m == 1, 1, PrimeOmega[m] == 1, 1+NN[PrimePi[m]], True, NN[r[m]]+NN[s[m]]-1]; row[n_] := Module[{A, k}, A = {}; For[k = F[n], k <= L[n], k++, If[NN[k] == n, A = Union[A, {k}]]]; A]; Table[row[n], {n, 1, 8}] // Flatten (* Jean-Fran├žois Alcover, Mar 06 2014, after Maple *)

nn=8; MGweight[n_]:=If[n===1, 1, 1+Total[Cases[FactorInteger[n], {p_, k_}:>k*MGweight[PrimePi[p]]]]];

Take[GatherBy[Range[Switch[nn, 1, 1, 2, 2, 3, 4, _, Nest[Prime, 8, nn-4]]], MGweight], nn] (* Gus Wiseman, Dec 21 2016 *)

CROSSREFS

Cf. A061775. Minimal and maximal entries in each row give A005517, A005518. Cf. A004111, A276625, A279065, A279614.

Sequence in context: A076564 A303550 A179892 * A125007 A290748 A035062

Adjacent sequences:  A061770 A061771 A061772 * A061774 A061775 A061776

KEYWORD

nonn,tabf,nice,easy

AUTHOR

N. J. A. Sloane, Jun 22 2001

EXTENSIONS

More terms from Emeric Deutsch, May 01 2004

STATUS

approved

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified December 13 10:42 EST 2018. Contains 318086 sequences. (Running on oeis4.)