

A061773


Triangle in which nth row lists MatulaGoebel 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.
nth 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 11correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141143.
I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131142.
D. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
Gus Wiseman, MatulaGoebel trees triangle illustration n=1..6
Index entries for sequences related to MatulaGoebel 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/31), Mod[n, 3] == 1, 5^(n/31/3), True, 9*5^(n/35/3)]; L[n_] := L[n] = Switch[n, 1, 1, 2, 2, 3, 4, 4, 8, _, Prime[L[n1]]]; 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 (* JeanFranç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, nn4]]], 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



