A349704 -id:A349704 - cp's OEIS frontend

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

Kevin Ryde, Nov 26 2021

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

			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,

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.

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

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

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

A133188 Natural numbers listed in three columns: if A004526(n-1) = 0 then row n lists A004526(n-1), A004526(n), 1, otherwise row n lists 1, A004526(n), A004526(n-1).

Original entry on oeis.org

0, 0, 1, 0, 1, 1, 1, 1, 1, 1, 2, 1, 1, 2, 2, 1, 3, 2, 1, 3, 3, 1, 4, 3, 1, 4, 4, 1, 5, 4, 1, 5, 5, 1, 6, 5, 1, 6, 6, 1, 7, 6, 1, 7, 7, 1, 8, 7, 1, 8, 8, 1, 9, 8, 1, 9, 9, 1, 10, 9, 1, 10, 10, 1, 11, 10, 1, 11, 11, 1, 12, 11, 1, 12, 12, 1, 13, 12, 1, 13, 13, 1, 14, 13, 1, 14, 14, 1, 15, 14, 1, 15, 15

Offset: 1

Paul Curtz, Oct 08 2007

The sum of row n is equal to n. See A004526 (integers repeated), which is the main entry for this sequence. - Omar E. Pol, Mar 19 2008

As a flat sequence, a(n+1) is the number of free trees of n vertices which have the maximum possible terminal Wiener index for n vertices (A349704). [Gutman, Furtula, Petrović, theorem 5] - Kevin Ryde, Nov 27 2021

			Rows begin:
  n=1:  0, 0, 1;
  n=2:  0, 1, 1;
  n=3:  1, 1, 1;
  n=4:  1, 2, 1;
  n=5:  1, 2, 2;
  n=6:  1, 3, 2;
        ...

Ivan Gutman, Boris Furtula and Miroslav Petrović, Terminal Wiener Index, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.

Cf. A004526, A349704 (maximum terminal Wiener).

Edited by Omar E. Pol, Mar 19 2008

cp's OEIS Frontend

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.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

PARI

Formula