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

 

Logo

Annual appeal: Please make a donation to keep the OEIS running! Over 6000 articles have referenced us, often saying "we discovered this result with the help of 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. 25
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: A070776 A076564 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 | More pages
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy .

Last modified December 13 09:05 EST 2017. Contains 295957 sequences.