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).
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
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 *)
PROG
(PARI) See links.
CROSSREFS
KEYWORD
nonn,tabf,nice,easy
AUTHOR
N. J. A. Sloane, Jun 22 2001
EXTENSIONS
More terms from Emeric Deutsch, May 01 2004
STATUS
approved