cp's OEIS Frontend

A184186 Irregular triangle read by rows: row n is the overall Wiener index vector of the rooted tree having Matula-Goebel number n (n>=2).

%I A184186 #9 Jan 07 2013 13:05:55
%S A184186 1,2,4,2,4,3,8,10,3,8,10,3,12,9,3,12,9,4,12,20,20,4,12,20,20,4,12,20,
%T A184186 20,4,16,29,18,4,16,29,18,4,16,29,18,5,16,30,40,35,4,24,36,16,4,16,29,
%U A184186 18,5,20,49,56,31,4,24,36,16,5,20,39,58,32,5,20,39
%N A184186 Irregular triangle read by rows: row n is the overall Wiener index vector of the rooted tree having Matula-Goebel number n (n>=2).
%C A184186 Component i (i>=1) of the overall Wiener index (number) vector of a graph G is defined as the sum of the Wiener numbers of all i-edge subgraphs of G (see the Bonchev reference, p. 583).
%C A184186 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 A184186 Number of entries in row n = 1st entry in row n = number of edges of the corresponding tree = A196050(n).
%C A184186 Last entry in row n = the Wiener index of the corresponding tree = A196051(n).
%C A184186 Sum of entries in row n = the overall Wiener index of the corresponding tree = A198340(n).
%C A184186 The Maple program yields row n with the command OWV(n) for n<=3000 (adjustable).
%D A184186 F. Goebel, On a 1-1-correspondence between rooted trees and natural numbers, J. Combin. Theory, B 29 (1980), 141-143.
%D A184186 I. Gutman and A. Ivic, On Matula numbers, Discrete Math., 150, 1996, 131-142.
%D A184186 I. Gutman and Yeong-Nan Yeh, Deducing properties of trees from their Matula numbers, Publ. Inst. Math., 53 (67), 1993, 17-22.
%D A184186 D. W. Matula, A natural rooted tree enumeration by prime factorization, SIAM Review, 10, 1968, 273.
%D A184186 D. Bonchev, The overall Wiener index - a new tool for characterization of molecular topology, J. Chem. Inf. Comput. Sci., 2001, 41, 582-592.
%H A184186 E. Deutsch, <a href="http://arxiv.org/abs/1111.4288"> Rooted tree statistics from Matula numbers</a>, arXiv:1111.4288
%F A184186 A198339(n) gives the sequence of the Matula-Goebel numbers of all the subtrees of the rooted tree with Matula-Goebel number n. A196051(k) is the Wiener number of the rooted tree with Matula-Goebel number k. A196050(k) is equal to the number of edges of the rooted tree with Matula-Goebel number k. In the Maple program we take the sum of the Wiener indices of all the subtrees, grouped according to number of edges.
%e A184186 Row n=5 is 3,8,10 because the rooted tree with Matula-Goebel number 5 is the path tree on 4 vertices; each of the three 1-edge subtrees has Wiener index 1, each of the two 2-edge subtrees has Wiener index 4 and the given 3-edge tree itself has Wiener index 10.
%e A184186 Triangle starts (n>=2):
%e A184186 1;
%e A184186 2,4;
%e A184186 2,4;
%e A184186 3,8,10;
%e A184186 3,8,10;
%e A184186 3,12,9;
%e A184186 3,12,9;
%e A184186 4,12,20,20;
%p A184186 m2union := proc (x, y) sort([op(x), op(y)]) end proc: with(numtheory); MRST := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then [1] elif bigomega(n) = 1 then [1, seq(ithprime(mrst[pi(n)][i]), i = 1 .. nops(mrst[pi(n)]))] else [seq(seq(mrst[r(n)][i]*mrst[s(n)][j], i = 1 .. nops(mrst[r(n)])), j = 1 .. nops(mrst[s(n)]))] end if end proc: MNRST := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc; if n = 1 then [] elif bigomega(n) = 1 then m2union(mrst[pi(n)], mnrst[pi(n)]) else m2union(mnrst[r(n)], mnrst[s(n)]) end if end proc: MST := proc (n) m2union(mrst[n], mnrst[n]) end proc: for n to 3000 do mrst[n] := MRST(n): mnrst[n] := MNRST(n): mst[n] := MST(n) end do: E := proc (n) local r, s: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: if n = 1 then 0 elif bigomega(n) = 1 then 1+E(pi(n)) else E(r(n))+E(s(n)) end if end proc: W := proc (n) local u, v, E, PL: u := proc (n) options operator, arrow: op(1, factorset(n)) end proc: v := proc (n) options operator, arrow: n/u(n) end proc: E := proc (n) if n = 1 then 0 elif bigomega(n) = 1 then 1+E(pi(n)) else E(u(n))+E(v(n)) end if end proc: PL := proc (n) if n = 1 then 0 elif bigomega(n) = 1 then 1+E(pi(n))+PL(pi(n)) else PL(u(n))+PL(v(n)) end if end proc: if n = 1 then 0 elif bigomega(n) = 1 then W(pi(n))+PL(pi(n))+1+E(pi(n)) else W(u(n))+W(v(n))+PL(u(n))*E(v(n))+PL(v(n))*E(u(n)) end if end proc: OWV := proc (n) local i, c, g, k: for i from 0 to E(n) do c[i] := 0 end do: g := MST(n): for k to nops(g) do c[E(g[k])] := c[E(g[k])]+W(g[k]) end do: seq(c[i], i = 1 .. E(n)) end proc:
%Y A184186 Cf. A196050, A196051, A198339, A198340.
%K A184186 nonn,tabf
%O A184186 2,2
%A A184186 _Emeric Deutsch_, Dec 04 2011