cp's OEIS Frontend

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

%I A206495 #9 Jan 06 2013 10:39:44
%S A206495 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,
%T A206495 15,18,21,21,15,20,22,26,34,22,29,31,41,59,18,18,20,24,28,23,26,29,37,
%U A206495 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
%N A206495 Irregular triangle read by rows: row n contains in nondecreasing order the Matula-Goebel numbers of the elements of N(t), where t is the rooted tree with Matula-Goebel number n and N is the natural growth operator.
%C A206495 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.
%C A206495 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.
%C A206495 Number of entries in row n is A061775(n).
%D A206495 A. Connes and D. Kreimer, Hopf algebras, renormalization and noncommutative geometry, Commun. Math. Phys., 199, 203-242, 1998.
%D A206495 Ch. Brouder, Runge-Kutta methods and renormalization, Eur. Phys. J. C 12, 521-534, 2000.
%D A206495 F. Panaite, Relating the Connes-Kreimer and Grossman-Larson Hopf algebras built on rooted trees, Letters Math. Phys., 51, 211-219, 2000.
%D A206495 F. Goebel, On a 1-1 correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
%D A206495 I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
%D A206495 I. Gutman and Y-N. Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
%D A206495 D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.
%H A206495 E. Deutsch, <a href="http://arxiv.org/abs/1111.4288">Rooted tree statistics from Matula numbers</a>, arXiv:1111.4288v1 [math.CO].
%F A206495 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.
%e A206495 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.
%e A206495 Triangle starts:
%e A206495 2;
%e A206495 3,4;
%e A206495 5,6,7;
%e A206495 6,6,8;
%e A206495 10,11,13,17;
%e A206495 9,10,12,14;
%p A206495 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
%Y A206495 Cf. A061775.
%K A206495 nonn,tabf
%O A206495 1,1
%A A206495 _Emeric Deutsch_, May 13 2012