login
Irregular triangle read by rows where T(n,k) is the maximum terminal Wiener index for a tree of n vertices among which k are leaves.
2

%I #13 Nov 28 2021 01:20:15

%S 0,0,1,2,3,6,4,8,12,5,10,16,20,6,12,20,26,30,7,14,24,32,39,42,8,16,28,

%T 38,48,54,56,9,18,32,44,57,66,72,72,10,20,36,50,66,78,88,92,90,11,22,

%U 40,56,75,90,104,112,115,110,12,24,44,62,84,102,120,132,140,140,132

%N Irregular triangle read by rows where T(n,k) is the maximum terminal Wiener index for a tree of n vertices among which k are leaves.

%C Gutman, Furtula, and Petrović, define the terminal Wiener index as the sum of the distances between all pairs of leaves (pendant vertices, degree 1) in a tree (or graph).

%C They determine the maximum terminal Wiener index T(n,k), and construct the trees which attain this maximum.

%C The triangle rows are all possible n,k combinations, which means k=n in rows n=0..2, and k=2..n-1 in rows n>=3.

%C The maximum within row n is A349704(n) and for n >= 8 this occurs at kmax = floor(2*n/3)+2 = A004523(n)+2 and equal maximum at kmax+1 when n == 1 (mod 3).

%H Kevin Ryde, <a href="/A349702/b349702.txt">Table of n, a(n) for n = 0..7023</a> (rows 0..120)

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

%F T(n,k) = k*(k-1) + (n-1-k)*floor(k/2)*ceiling(k/2). [Gutman, Furtula, Petrović, theorem 4]

%F G.f.: x^2*y^2*( 1 + x*(1 + (1-x)*(1+2*x*y)) / ((1-x)^2 * (1+x*y) * (1-x*y)^3) ).

%e Triangle begins:

%e k=0 1 2 3 4 5 6 7 8

%e n=0; 0,

%e n=1; 0,

%e n=2; 1,

%e n=3; 2,

%e n=4; 3, 6,

%e n=5; 4, 8, 12,

%e n=6; 5, 10, 16, 20,

%e n=7; 6, 12, 20, 26, 30,

%e n=8; 7, 14, 24, 32, 39, 42,

%e n=9; 8, 16, 28, 38, 48, 54, 56,

%o (PARI) T(n,k) = (((n-k+3)*k - 4)*k + if(k%2,k-n+1))>>2;

%Y Cf. A349703 (number of trees), A349704 (row maxima).

%K easy,nonn,tabf

%O 0,4

%A _Kevin Ryde_, Nov 26 2021