A257540 Irregular triangle read by rows: row n (n>=2) contains the degrees of the level 1 vertices of the rooted tree having Matula-Goebel number n; row 1: 0.

0, 1, 2, 1, 1, 2, 1, 2, 3, 1, 1, 1, 2, 2, 1, 2, 2, 1, 1, 2, 3, 1, 3, 2, 2, 1, 1, 1, 1, 2, 1, 2, 2, 4, 1, 1, 2, 2, 3, 1, 2, 3, 1, 1, 1, 2, 2, 2, 1, 3, 2, 2, 2, 1, 1, 3, 3, 1, 2, 2, 2, 1, 1, 1, 1, 1, 2, 2, 1, 2, 2, 3, 1, 1, 2, 2, 4, 1, 4, 2, 3, 1, 1

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

Table of n, a(n) for n=1..83.

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

Cf. A196052, A001222.

Sequence in context: A340260 A175190 A317685 * A333516 A228202 A308972

Adjacent sequences: A257537 A257538 A257539 * A257541 A257542 A257543

Keyword

nonn,tabf

Author

Emeric Deutsch, May 04 2015

Status

approved