1,1

The natural growth operator maps a rooted tree t with V(t) vertices to the sequence of V(t) rooted trees, each having 1+V(t) vertices, by attaching one more outgoing edge and vertex to each vertex of t (the root remains the same). See, for example, the Brouder reference, p. 522 or the Connes-Kreimer reference, p. 225.

The 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 A061775(n).

A. Connes and D. Kreimer, Hopf algebras, renormalization and noncommutative geometry, Commun. Math. Phys., 199, 203-242, 1998.

Ch. Brouder, Runge-Kutta methods and renormalization, Eur. Phys. J. C 12, 521-534, 2000.

F. Panaite, Relating the Connes-Kreimer and Grossman-Larson Hopf algebras built on rooted trees, Letters Math. Phys., 51, 211-219, 2000.

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 Y-N. 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 Review, 10, 1968, 273.

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

E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288v1 [math.CO].

Denote the natural growth operator by NG. It is convenient to introduce a "modified natural growth operator" MNG, defined just like NG, except that no edge is attached to the root. By NG(k) and MNG(k) we mean the action of these operators on the tree with Matula-Goebel number k. (i) NG(n) = [2n, MNG(n)]; (ii) MNG(1) = [ ]; (iii) if NG(t) = [a,b,c,...], then MNG(t-th prime) = [a-th prime, b-th prime, c-th prime, ...]; if r,s,>=2, then NG(rs) = [2rs, r multiplied by the elements of MNG(s); s multiplied by the elements of MNG(r)]. The Maple program is based on these recurrence relations.

Row 2 is 3,4 because the rooted tree with Matula-Goebel number 2 is the 1-edge tree; attaching one edge at each vertex, we obtain \/ and the 2-edge path, having Matula-Goebel numbers 4 and 3, respectively.

Triangle starts:

2;

3,4;

5,6,7;

6,6,8;

10,11,13,17;

9,10,12,14;

with(numtheory): b := proc (n) local r, s, a: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: a := proc (n) options operator, arrow: [2*n, seq(b(n)[j], j = 1 .. nops(b(n)))] end proc: if n = 1 then [] elif bigomega(n) = 1 then map(ithprime, a(pi(n))) else [seq(r(n)*b(s(n))[j], j = 1 .. nops(b(s(n)))), seq(s(n)*b(r(n))[j], j = 1 .. nops(b(r(n))))] end if end proc: a := proc (n) options operator, arrow: sort([2*n, seq(b(n)[j], j = 1 .. nops(b(n)))]) end proc: for n to 20 do a(n) end do; # yields sequence in triangular form

Cf. A061775.

Sequence in context: A017892 A017882 A017872 * A161209 A279513 A000026

Adjacent sequences: A206492 A206493 A206494 * A206496 A206497 A206498

nonn,tabf

Emeric Deutsch, May 13 2012

approved