A180569 -id:A180569 - cp's OEIS frontend

A143368 Triangle read by rows: T(n,k) is the Wiener index of a k X n grid (i.e., P_k X P_n, where P_m is the path graph on m vertices; 1 <= k <= n).

0, 1, 8, 4, 25, 72, 10, 56, 154, 320, 20, 105, 280, 570, 1000, 35, 176, 459, 920, 1595, 2520, 56, 273, 700, 1386, 2380, 3731, 5488, 84, 400, 1012, 1984, 3380, 5264, 7700, 10752, 120, 561, 1404, 2730, 4620, 7155, 10416, 14484, 19440

Offset: 1

Emeric Deutsch, Sep 05 2008

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.

			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;

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

Cf. A180569 (row 3), A131423 (row 2).
Main diagonal is A143945.
Cf. A245826.

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

Table[k n (n + k) (k n - 1)/6, {n, 9}, {k, n}] // Flatten (* Michael De Vlieger, May 28 2017 *)

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

T(n,k) = k*n*(n+k)*(k*n-1)/6 (k, n >= 1).

A180568 Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the grid P_3 x P_n (1<=k<=n), where P_j denotes the path graph on j nodes.

Original entry on oeis.org

2, 1, 7, 6, 2, 12, 14, 8, 2, 17, 22, 17, 8, 2, 22, 30, 26, 17, 8, 2, 27, 38, 35, 26, 17, 8, 2, 32, 46, 44, 35, 26, 17, 8, 2, 37, 54, 53, 44, 35, 26, 17, 8, 2, 42, 62, 62, 53, 44, 35, 26, 17, 8, 2, 47, 70, 71, 62, 53, 44, 35, 26, 17, 8, 2, 52, 78, 80, 71, 62, 53, 44, 35, 26, 17, 8, 2, 57

Offset: 1

Emeric Deutsch, Sep 28 2010

Row n contains n+1 entries.
Sum of entries in row n = (3/2)n(3n-1)=A062741(n).
The entries in row n are the coefficients of the Wiener polynomial of the grid P_3 x P_n.
Sum(k*T(n,k),k=1..n+1)=(1/2)n(n+3)(3n-1)=A180569(n) = the Wiener index of the grid P_3 x P_n.
The average of all distances in the grid P_3 x P_n is (n+3)/3.

			T(1,1)=2, T(1,2)=1 because in P_3 x P_1 = P_3 there are 2 pairs of nodes at distance 1 and one pair at distance 2.
Triangle starts:
2,1;
7,6,2;
12,14,8,2;
17,22,17,8,2;

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.

Cf. A180569

p := proc (n) options operator, arrow: (t^(n+1)*(3+4*t+2*t^2)+(5*n-3)*t-(2*n+4)*t^2-(2*n+2)*t^3-n*t^4)/(1-t)^2 end proc: for n to 12 do f[n] := sort(expand(simplify(p(n)))) end do: for n to 12 do seq(coeff(f[n], t, k), k = 1 .. n+1) end do; # yields sequence in triangular form

The row generating polynomials p(n)=p(n,t) satisfy the recurrence relation p(n)=p(n-1)=2t+t^2+t(3+4t+2t^2)*sum(t^j,j=0..n-2) (these are the Wiener polynomials of the corresponding graphs).
The generating polynomial of row n is p(n; t)=[t^{n+1}*(3+4t+2t^2)+(5n-3)t-2(n+2)t^2-2(n+1)t^3-nt^4]/(1-t)^2.
G.f. = G(t,z)=Sum(T(n,k)*t^k*z^n, k>=1, n>=1) = tz(zt^2+2tz+t+3z+2)/[(1-tz)(1-z)^2].

A180865 Square array read by antidiagonals: T(m,n) is the Wiener index of the stacked book graph B(m,n) (m>=1, n>=1). B(m,n) is defined as the graph Cartesian product S(m+1) x P(n), where S(m+1) is the star graph on m+1 nodes and P(n) is the path graph on n nodes. The Wiener index of a connected graph is the sum of distances between all unordered pairs of nodes in the graph.

Original entry on oeis.org

1, 4, 8, 9, 25, 25, 16, 52, 72, 56, 25, 89, 145, 154, 105, 36, 136, 244, 304, 280, 176, 49, 193, 369, 506, 545, 459, 273, 64, 260, 520, 760, 900, 884, 700, 400, 81, 337, 697, 1066, 1345, 1451, 1337, 1012, 561, 100, 424, 900, 1424, 1880, 2160, 2184, 1920, 1404, 760

Offset: 1

Emeric Deutsch, Sep 28 2010

T(1,n) = A131423(n).

T(2,n) = A180569(n).

			T(2,1)=4 because B(2,1) reduces to the path graph P(3) which has 2 pairs of nodes at distance 1 and 1 pair at distance 2.
Square array T(m,n) begins:
1, 8, 25, 56, 105, ...
4, 25, 72, 154, 280, ...
9, 52, 145, 304, 545, ...
16, 89, 244, 506, 900, ...

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, Stacked Book Graph.

Cf. A131423, A180569.

T := proc (m, n) options operator, arrow: (1/6)*n*(n^2-(m+1)^2+m*n*(m*n+2*n+6*m)) end proc: for n to 10 do seq(T(n+1-j, j), j = 1 .. n) end do; # yields sequence in triangular form

T(m,n) = (1/6)n[n^2-(m+1)^2+mn(mn+6m+2n)].

The Wiener polynomial p[n](t) of the graph B(m,n) satisfies the recurrence relation p[n] = p[n-1]+mt+(1/2)m(m-1)t^2+[t+mt+2mt^2+m(m-1)t^3]*sum(t^j,j=0..n-2).

cp's OEIS Frontend

A143368 Triangle read by rows: T(n,k) is the Wiener index of a k X n grid (i.e., P_k X P_n, where P_m is the path graph on m vertices; 1 <= k <= n).

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Mathematica

PARI

Formula

A180568 Triangle read by rows: T(n,k) is the number of unordered pairs of nodes at distance k in the grid P_3 x P_n (1<=k<=n), where P_j denotes the path graph on j nodes.

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula

Views

Author

Keywords

Comments

Examples

Links

Crossrefs

Programs

Maple

Formula