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

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, 38, 48, 54, 56, 9, 18, 32, 44, 57, 66, 72, 72, 10, 20, 36, 50, 66, 78, 88, 92, 90, 11, 22, 40, 56, 75, 90, 104, 112, 115, 110, 12, 24, 44, 62, 84, 102, 120, 132, 140, 140, 132

Offset: 0

Author

Kevin Ryde, Nov 26 2021

Keywords

• easy
• nonn
• tabf

Comments

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

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

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.

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

Examples

			Triangle begins:
      k=0  1  2   3   4   5   6   7   8
  n=0;  0,
  n=1;     0,
  n=2;        1,
  n=3;        2,
  n=4;        3,  6,
  n=5;        4,  8, 12,
  n=6;        5, 10, 16, 20,
  n=7;        6, 12, 20, 26, 30,
  n=8;        7, 14, 24, 32, 39, 42,
  n=9;        8, 16, 28, 38, 48, 54, 56,
		

Links

• Kevin Ryde, Table of n, a(n) for n = 0..7023 (rows 0..120)
• Ivan Gutman, Boris Furtula and Miroslav Petrović, Terminal Wiener Index, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.

Crossrefs

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

Programs

PARI

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

Formula

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

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