A349703 Irregular triangle read by rows where T(n,k) is the number of free trees attaining the maximum terminal Wiener index (A349702) for a tree of n vertices among which k are leaves.

1, 1, 1, 1, 1, 1, 1, 1, 1, 1, 2, 1, 1, 1, 3, 1, 1, 1, 1, 4, 1, 2, 1, 1, 1, 5, 1, 2, 1, 1, 1, 1, 7, 1, 3, 1, 2, 1, 1, 1, 8, 1, 3, 1, 2, 1, 1, 1, 1, 10, 1, 4, 1, 3, 1, 2, 1, 1, 1, 12, 1, 4, 1, 3, 1, 2, 1, 1, 1, 1, 14, 1, 5, 1, 4, 1, 3, 1, 2, 1, 1, 1, 16, 1, 5, 1, 4, 1, 3, 1, 2, 1, 1, 1

Offset: 0

Author

Kevin Ryde, Nov 26 2021

Keywords

• easy
• nonn
• tabf

Comments

Gutman, Furtula, and Petrović determine the maximum terminal Wiener index (A349702) possible in trees, 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.

For k even, a unique tree has the maximum index.

For k=3, all trees have the same index.

Examples

			Triangle begins
      k=0  1  2  3  4  5  6  7  8
  n=0;  1,
  n=1;     1,
  n=2;        1,
  n=3;        1,
  n=4;        1, 1,
  n=5;        1, 1, 1,
  n=6;        1, 2, 1, 1,
  n=7;        1, 3, 1, 1, 1,
  n=8;        1, 4, 1, 2, 1, 1,
  n=9;        1, 5, 1, 2, 1, 1, 1,
For n=9,k=5, the T(9,5) = 2 trees are
  *--*--*--*--*--*     *--*--*--*--*--*
    /|         \         /   |      \
   * *          *       *    *       *
		

Links

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

Crossrefs

Cf. A349702 (maximum index), A055290 (count all trees), A001399 (trees k=3 leaves).

Programs

PARI

T(n,k) = if(n==1||k%2==0,1, k==3,(n-1)^2\/12, (n-k+1)>>1);

Formula

T(n,3) = A055290(n,3) = A001399(n-4) = round((n-1)^2 / 12).

T(n,k) = 1 for k even. [Gutman, Furtula, Petrović, theorem 4 (a)]

T(n,k) = ceiling((n-k)/2) for odd k >= 5. [Gutman, Furtula, Petrović, theorem 4 (b)]

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