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

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.

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.

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

Example

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
  *--*--*--*--*--*     *--*--*--*--*--*
    /|         \         /   |      \
   * *          *       *    *       *

Prog

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

Crossrefs

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

Sequence in context: A294306 A181348 A107682 * A178239 A260534 A350103

Adjacent sequences: A349700 A349701 A349702 * A349704 A349705 A349706

Keyword

easy,nonn,tabf

Author

Kevin Ryde, Nov 26 2021

Status

approved