A196066 - OEIS

%I #14 Jun 22 2024 10:33:54

%S 0,0,2,2,8,8,3,3,20,20,20,12,12,12,40,4,12,29,4,28,28,40,29,17,70,29,

%T 36,16,28,55,40,5,70,28,53,40,17,17,55,38,29,38,16,53,68,36,55,23,36,

%U 93,53,38,5,48,112,21,38,55,28,73,40,70,45,6,92,92,17,36,68,70,38,53,38,40,114,21,89,72,53,50

%N The reverse Wiener index of the rooted tree with Matula-Goebel number n.

%C The reverse Wiener index of a connected graph is (1/2)N(N-1)D - W, where N, D, and W are, respectively, the number of vertices, the diameter, and the Wiener index of the graph.

%C The Matula-Goebel number of a rooted tree is 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.

%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 Yeong-Nan 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.

%D A. T. Balaban, D. Mills, O. Ivanciuc, and S. C. Basak, Reverse Wiener indices, Croatica Chemica Acta, 73 (4), 2000, 923-941.

%H <a href="/index/Mat#matula">Index entries for sequences related to Matula-Goebel numbers</a>

%F a(n)=(1/2)N(n)*(N(n)-1)*d(n) - W(n),  where N, d, and W are, respectively, the number of vertices, the diameter, and the Wiener index of the rooted tree with Matula-Goebel number n  (all these data are contained in the Wiener polynomial; see A196059). The Maple program is based on the above.

%e a(7)=3 because the rooted tree with Matula-Goebel number 7 is the rooted tree Y with N=4, d=2, W=9 (distances are 1,1,1,2,2,2); (1/2)*4*3*2-9 = 3.

%p with(numtheory): Wp := proc (n) local r, s, R: r := proc (n) options operator, arrow: op(1, factorset(n)) end proc: s := proc (n) options operator, arrow: n/r(n) end proc: R := proc (n) if n = 1 then 0 elif bigomega(n) = 1 then sort(expand(x*R(pi(n))+x)) else sort(expand(R(r(n))+R(s(n)))) end if end proc: if n = 1 then 0 elif bigomega(n) = 1 then sort(expand(Wp(pi(n))+x*R(pi(n))+x)) else sort(expand(Wp(r(n))+Wp(s(n))+R(r(n))*R(s(n)))) end if end proc: N := proc (n) options operator, arrow: 1+coeff(Wp(n), x) end proc: d := proc (n) options operator, arrow: degree(Wp(n)) end proc: W := proc (n) options operator, arrow: subs(x = 1, diff(Wp(n), x)) end proc: a := proc (n) options operator, arrow: (1/2)*N(n)*(N(n)-1)*d(n)-W(n) end proc: 0, seq(a(n), n = 2 .. 80);

%t r[n_] := FactorInteger[n][[1, 1]];

%t s[n_] := n/r[n];

%t R[n_] := Which[n == 1, 0, PrimeOmega[n] == 1, x*R[PrimePi[n]] + x, True,  R[r[n]] + R[s[n]]];

%t Wp[n_] := Which[n == 1, 0, PrimeOmega[n] == 1, Wp[PrimePi[n]] + x*R[PrimePi[n]] + x, True, Wp[r[n]] + Wp[s[n]] + R[r[n]]*R[s[n]]];

%t V[n_] := 1 + Coefficient[Wp[n], x];

%t d[n_] := Exponent[Wp[n], x];

%t W[n_] := D[Wp[n], x] /. x -> 1;

%t a[n_] := If[n == 1, 0, (1/2)*V[n]*(V[n] - 1)*d[n] - W[n]];

%t Table[a[n], {n, 1, 80}] (* _Jean-François Alcover_, Jun 22 2024, after Maple code *)

%Y Cf. A196059.

%K nonn

%O 1,3

%A _Emeric Deutsch_, Oct 01 2011