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,4

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

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.

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

Example

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,

Prog

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

Crossrefs

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

Sequence in context: A302023 A112975 A257218 * A289055 A109890 A370046

Adjacent sequences: A349699 A349700 A349701 * A349703 A349704 A349705

Keyword

easy,nonn,tabf

Author

Kevin Ryde, Nov 26 2021

Status

approved