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).

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, 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, 18, 5, 20, 49, 56, 31, 4, 24, 36, 16, 5, 20, 39, 58, 32, 5, 20, 39

Offset: 2

Author

Emeric Deutsch, Dec 04 2011

Keywords

• nonn
• tabf

Comments

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).

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 = 1st entry in row n = number of edges of the corresponding tree = A196050(n).

Last entry in row n = the Wiener index of the corresponding tree = A196051(n).

Sum of entries in row n = the overall Wiener index of the corresponding tree = A198340(n).

The Maple program yields row n with the command OWV(n) for n<=3000 (adjustable).

Examples

			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.
Triangle starts (n>=2):
1;
2,4;
2,4;
3,8,10;
3,8,10;
3,12,9;
3,12,9;
4,12,20,20;
		

References

• 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 Yeong-Nan 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.
• D. Bonchev, The overall Wiener index - a new tool for characterization of molecular topology, J. Chem. Inf. Comput. Sci., 2001, 41, 582-592.

Links

• E. Deutsch, Rooted tree statistics from Matula numbers, arXiv:1111.4288

Crossrefs

Cf. A196050, A196051, A198339, A198340.

Programs

Maple

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:

Formula

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.