login
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.
3
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
KEYWORD
easy,nonn,tabf
AUTHOR
Kevin Ryde, Nov 26 2021
STATUS
approved