OFFSET
1,3
COMMENTS
The Matula (or Matula-Goebel) number of a rooted tree can be defined in the following recursive manner: to the one-vertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the t-th prime number, where t is the Matula-Goebel number of the tree obtained from T by deleting the edge emanating from the root; to a tree T with root degree m>=2 there corresponds the product of the Matula-Goebel numbers of the m branches of T.
Number of entries in row n is the number of prime divisors of n counted with multiplicity.
Sum of entries in row n = A196052(n).
LINKS
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288 [math.CO], 2011.
E. Deutsch, Rooted tree statistics from Matula numbers, Discrete Appl. Math., 160, 2012, 2314-2322.
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.
I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Rev. 10 (1968) 273.
FORMULA
Denoting by DL(n) the multiset of the degrees of the level 1 vertices of the rooted tree with Matula number n, we have DL(1)=[0], DL[2]=[1], DL(i-th prime) = [1+bigomega(i)], DL(rs) = DL(r) union DL(s), where bigomega(i) is the number of prime divisors of i, counted with multiplicity (A001222) and "union" is "multiset union". The Maple program is based on these recurrence equations.
EXAMPLE
Row 8 is 1,1,1. Indeed, the rooted tree with Matula number 8 is the star tree \|/; vertices at level 1 have degrees 1,1,1.
Triangle starts:
0;
1;
2;
1,1;
2;
1,2;
3;
1,1,1;
MAPLE
with(numtheory): DL := proc (n) if n = 2 then [1] elif bigomega(n) = 1 then [1+bigomega(pi(n))] else [op(DL(op(1, factorset(n)))), op(DL(n/op(1, factorset(n))))] end if end proc: with(numtheory): DL := proc (n) if n = 1 then [0] elif n = 2 then [1] elif bigomega(n) = 1 then [1+bigomega(pi(n))] else [op(DL(op(1, factorset(n)))), op(DL(n/op(1, factorset(n))))] end if end proc: seq(op(DL(n)), n = 1 .. 100);
CROSSREFS
KEYWORD
nonn,tabf
AUTHOR
Emeric Deutsch, May 04 2015
STATUS
approved