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