

A143944


Triangle read by rows: T(n,k) is the number of unordered pairs of vertices at distance k from each other in the grid P_n X P_n (1 <= k <= 2n2), where P_n is the path graph on n vertices.


1



4, 2, 12, 14, 8, 2, 24, 34, 32, 20, 8, 2, 40, 62, 68, 60, 40, 20, 8, 2, 60, 98, 116, 116, 100, 70, 40, 20, 8, 2, 84, 142, 176, 188, 180, 154, 112, 70, 40, 20, 8, 2, 112, 194, 248, 276, 280, 262, 224, 168, 112, 70, 40, 20, 8, 2, 144, 254, 332, 380, 400, 394, 364, 312, 240
(list;
graph;
refs;
listen;
history;
text;
internal format)



OFFSET

2,1


COMMENTS

Row n contains 2n2 entries.
Sum of entries in row n = n^2*(n^2  1)/2 = A083374(n).
The entries in row n are the coefficients of the Wiener (Hosoya) polynomial of the grid P_n X P_n.
Sum_{k=1..2n2} k*T(n,k) = n^3*(n^2  1)/3 = A143945(n) = the Wiener index of the grid P_n X P_n.
The average of all distances in the grid P_n X P_n is 2n/3.


LINKS

Table of n, a(n) for n=2..66.
D. Stevanovic, Hosoya polynomial of composite graphs, Discrete Math., 235 (2001), 237244.
B.Y. Yang and Y.N. Yeh, Wiener polynomials of some chemically interesting graphs, International Journal of Quantum Chemistry, 99 (2004), 8091.
Y.N. Yeh and I. Gutman, On the sum of all distances in composite graphs, Discrete Math., 135 (1994), 359365.


FORMULA

Generating polynomial of row n is (2q(1q^n)  n(1q^2))^2/(2(1q)^4)  n^2/2.


EXAMPLE

T(2,2)=2 because P_2 X P_2 is a square and there are 2 pairs of vertices at distance 2.
Triangle starts:
4, 2;
12, 14, 8, 2;
24, 34, 32, 20, 8, 2;
40, 62, 68, 60, 40, 20, 8, 2;


MAPLE

for n from 2 to 10 do Q[n]:=sort(expand(simplify((1/2)*(2*q*(1q^n)n*(1q^2))^2/(1q)^4(1/2)*n^2))) end do: for n from 2 to 9 do seq(coeff(Q[n], q, j), j= 1..2*n2) end do;


CROSSREFS

Cf. A083374, A143945.
Sequence in context: A111667 A323825 A019239 * A154345 A058095 A105196
Adjacent sequences: A143941 A143942 A143943 * A143945 A143946 A143947


KEYWORD

nonn,tabf


AUTHOR

Emeric Deutsch, Sep 19 2008


STATUS

approved



