

A206495


Irregular triangle read by rows: row n contains in nondecreasing order the MatulaGoebel numbers of the elements of N(t), where t is the rooted tree with MatulaGoebel number n and N is the natural growth operator.


1



2, 3, 4, 5, 6, 7, 6, 6, 8, 10, 11, 13, 17, 9, 10, 12, 14, 13, 13, 14, 19, 12, 12, 12, 16, 15, 15, 18, 21, 21, 15, 20, 22, 26, 34, 22, 29, 31, 41, 59, 18, 18, 20, 24, 28, 23, 26, 29, 37, 43, 21, 26, 26, 28, 38, 25, 30, 33, 35, 39, 51, 24, 24, 24, 24, 32, 34, 41, 41, 43, 67, 27, 30, 30, 36, 42, 42, 37, 37, 37, 38, 53, 30, 30, 40, 44, 52, 68
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

1,1


COMMENTS

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 ConnesKreimer reference, p. 225.
The MatulaGoebel number of a rooted tree can be defined in the following recursive manner: to the onevertex tree there corresponds the number 1; to a tree T with root degree 1 there corresponds the tth prime number, where t is the MatulaGoebel 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 MatulaGoebel numbers of the m branches of T.
Number of entries in row n is A061775(n).


REFERENCES

A. Connes and D. Kreimer, Hopf algebras, renormalization and noncommutative geometry, Commun. Math. Phys., 199, 203242, 1998.
Ch. Brouder, RungeKutta methods and renormalization, Eur. Phys. J. C 12, 521534, 2000.
F. Panaite, Relating the ConnesKreimer and GrossmanLarson Hopf algebras built on rooted trees, Letters Math. Phys., 51, 211219, 2000.
F. Goebel, On a 11 correspondence 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.
I. Gutman and YN. Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 1722.
D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.


LINKS

Table of n, a(n) for n=1..88.
E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288v1 [math.CO].


FORMULA

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 MatulaGoebel number k. (i) NG(n) = [2n, MNG(n)]; (ii) MNG(1) = [ ]; (iii) if NG(t) = [a,b,c,...], then MNG(tth prime) = [ath prime, bth prime, cth 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.


EXAMPLE

Row 2 is 3,4 because the rooted tree with MatulaGoebel number 2 is the 1edge tree; attaching one edge at each vertex, we obtain \/ and the 2edge path, having MatulaGoebel numbers 4 and 3, respectively.
Triangle starts:
2;
3,4;
5,6,7;
6,6,8;
10,11,13,17;
9,10,12,14;


MAPLE

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


CROSSREFS

Cf. A061775.
Sequence in context: A017892 A017882 A017872 * A161209 A279513 A000026
Adjacent sequences: A206492 A206493 A206494 * A206496 A206497 A206498


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, May 13 2012


STATUS

approved



