%I #12 Nov 28 2021 01:20:23
%S 0,0,1,2,6,12,20,30,42,56,72,92,115,140,170,204,240,282,329,378,434,
%T 496,560,632,711,792,882,980,1080,1190,1309,1430,1562,1704,1848,2004,
%U 2171,2340,2522,2716,2912,3122,3345,3570,3810,4064,4320,4592,4879,5168,5474
%N Maximum terminal Wiener index for a tree of n vertices.
%C Gutman, Furtula, and Petrović, define the terminal Wiener index as the sum of the distances between all pairs of pendant vertices (leaves, degree 1) in a tree (or graph).
%C They determine the maximum terminal Wiener index for trees of n vertices and construct the trees which attain this maximum.
%C For n<=9 the star-n uniquely attains the maximum, and beyond that there are certain cases according as n mod 3.
%H Kevin Ryde, <a href="/A349704/b349704.txt">Table of n, a(n) for n = 0..5000</a>
%H Ivan Gutman, Boris Furtula and Miroslav Petrović, <a href="https://doi.org/10.1007/s10910-008-9476-2">Terminal Wiener Index</a>, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.
%H <a href="/index/Rec#order_08">Index entries for linear recurrences with constant coefficients</a>, signature (2,-1,2,-4,2,-1,2,-1).
%F a(0) = a(1) = a(2) = 1, a(n) = (n-1)*(n-2) for 3 <= n <= 9, and otherwise: [Gutman, Furtula, Petrović, theorem 5]
%F a(3s) = s^3 + 3*s^2 + s - 1,
%F a(3s+1) = s^3 + 4*s^2 + 3*s,
%F a(3s+2) = s^3 + 5*s^2 + 6*s + 2.
%F a(n) = 2*a(n-1) - a(n-2) + 2*a(n-3) - 4*a(n-4) + 2*a(n-5) - a(n-6) + 2*a(n-7) - a(n-8) for n>=15.
%F G.f.: 1 - x^2 - 2*x^3 - 2*x^4 - 2*x^5 - x^6 + (-1 + 2*x + x^2 + 2*x^3 - 2*x^4) / ((1-x)^4*(1+x+x^2)^2).
%o (PARI) a(n) = if(n<4,max(0,n-1), n<7,(n-1)*(n-2), (((n+9)*n + if(n%3,6,9))*n - 1)\27);
%Y Cf. A133188 (number of trees attaining), A349703 (maximum by leaves).
%K easy,nonn
%O 0,4
%A _Kevin Ryde_, Nov 26 2021