A061773 Triangle in which n-th row lists Matula-Goebel numbers for all rooted trees with n nodes.

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

Offset: 1

Author

N. J. A. Sloane, Jun 22 2001

Keywords

• nonn
• tabf
• nice
• easy

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).

Examples

			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
		

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.
• Kevin Ryde, PARI/GP code calculating rows
• Gus Wiseman, Matula-Goebel trees triangle illustration n=1..6
• Index entries for sequences related to Matula-Goebel numbers
• Index entries for sequences that are permutations of the natural numbers
• Index entries for sequences related to rooted trees
• Index entries for sequences related to trees

Crossrefs

Cf. A061775 (number of nodes), A000081 (row lengths), A005517 (row minimum), A005518 (row maximum), A214572 (row n=8).

Cf. A347620 (inverse permutation).

Cf. A276625, A279065, A279614.

Programs

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 *)

PARI

\\ See links.

Extensions

More terms from Emeric Deutsch, May 01 2004