OFFSET
1,3
COMMENTS
The Wiener index of a connected graph is the sum of distances between all unordered pairs of vertices in the graph.
This is the lower triangular half of a symmetric square array.
LINKS
Michael De Vlieger, Table of n, a(n) for n = 1..11325 (rows 1 <= n <= 150).
A. Graovac and T. Pisanski, On the Wiener index of a graph, J. Math. Chem., 8 (1991), 53-62.
B. E. Sagan, Y-N. Yeh and P. Zhang, The Wiener Polynomial of a Graph, Internat. J. of Quantum Chem., 60, 1996, 959-969.
Eric Weisstein's World of Mathematics, Grid Graph
Eric Weisstein's World of Mathematics, Wiener Index
FORMULA
T(n,k) = k*n*(n+k)*(k*n-1)/6 (k, n >= 1).
EXAMPLE
Presentation as symmetric square array starts:
======================================================
n\k| 1 2 3 4 5 6 7 8 9
---|--------------------------------------------------
1 | 0 1 4 10 20 35 56 84 120 ...
2 | 1 8 25 56 105 176 273 400 561 ...
3 | 4 25 72 154 280 459 700 1012 1404 ...
4 | 10 56 154 320 570 920 1386 1984 2730 ...
5 | 20 105 280 570 1000 1595 2380 3380 4620 ...
6 | 35 176 459 920 1595 2520 3731 5264 7155 ...
7 | 56 273 700 1386 2380 3731 5488 7700 10416 ...
8 | 84 400 1012 1984 3380 5264 7700 10752 14484 ...
9 | 120 561 1404 2730 4620 7155 10416 14484 19440 ...
... - Andrew Howroyd, May 27 2017
T(2,2)=8 because in a square we have four distances equal to 1 and two distances equal to 2.
T(2,1)=1 because on the path graph on two vertices there is one distance equal to 1.
T(3,2)=25 because on the P(2) X P(3) graph there are 7 distances equal to 1, 6 distances equal to 2 and 2 distances equal to 3, with 7*1 + 6*2 + 2*3 = 25.
Triangle starts: 0; 1,8; 4,25,72; 10,56,154,320;
MAPLE
T:=proc(n, k) options operator, arrow: (1/6)*k*n*(n+k)*(k*n-1) end proc: for n to 9 do seq(T(n, k), k=1..n) end do; # yields sequence in triangular form
MATHEMATICA
Table[k n (n + k) (k n - 1)/6, {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, May 28 2017 *)
PROG
(PARI)
T(n, k)=k*n*(n+k)*(k*n-1)/6;
for (n=1, 8, for(k=1, 8, print1(T(n, k), ", ")); print) \\ Andrew Howroyd, May 27 2017
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Emeric Deutsch, Sep 05 2008
STATUS
approved