|
|
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
(list;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
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
|
Ivan Gutman, Boris Furtula and Miroslav Petrović, Terminal Wiener Index, Journal of Mathematical Chemistry, volume 46, 2009, pages 522-531.
|
|
FORMULA
|
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
|
|
|
KEYWORD
|
easy,nonn,tabf
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|