|
%I #14 Jun 12 2022 14:07:11
%S 4,2,12,14,8,2,24,34,32,20,8,2,40,62,68,60,40,20,8,2,60,98,116,116,
%T 100,70,40,20,8,2,84,142,176,188,180,154,112,70,40,20,8,2,112,194,248,
%U 276,280,262,224,168,112,70,40,20,8,2,144,254,332,380,400,394,364,312,240
%N 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 <= 2n-2), where P_n is the path graph on n vertices.
%C Row n contains 2n-2 entries.
%C Sum of entries in row n = n^2*(n^2 - 1)/2 = A083374(n).
%C The entries in row n are the coefficients of the Wiener (Hosoya) polynomial of the grid P_n X P_n.
%C Sum_{k=1..2n-2} k*T(n,k) = n^3*(n^2 - 1)/3 = A143945(n) = the Wiener index of the grid P_n X P_n.
%C The average of all distances in the grid P_n X P_n is 2n/3.
%H D. Stevanovic, <a href="https://doi.org/10.1016/S0012-365X(00)00277-6">Hosoya polynomial of composite graphs</a>, Discrete Math., 235 (2001), 237-244.
%H B.-Y. Yang and Y.-N. Yeh, <a href="http://www.iis.sinica.edu.tw/papers/byyang/2387-F.pdf">Wiener polynomials of some chemically interesting graphs</a>, International Journal of Quantum Chemistry, 99 (2004), 80-91.
%H Y.-N. Yeh and I. Gutman, <a href="http://dx.doi.org/10.1016/0012-365X(93)E0092-I">On the sum of all distances in composite graphs</a>, Discrete Math., 135 (1994), 359-365.
%F Generating polynomial of row n is (2q(1-q^n) - n(1-q^2))^2/(2(1-q)^4) - n^2/2.
%e T(2,2)=2 because P_2 X P_2 is a square and there are 2 pairs of vertices at distance 2.
%e Triangle starts:
%e 4, 2;
%e 12, 14, 8, 2;
%e 24, 34, 32, 20, 8, 2;
%e 40, 62, 68, 60, 40, 20, 8, 2;
%p for n from 2 to 10 do Q[n]:=sort(expand(simplify((1/2)*(2*q*(1-q^n)-n*(1-q^2))^2/(1-q)^4-(1/2)*n^2))) end do: for n from 2 to 9 do seq(coeff(Q[n],q,j),j= 1..2*n-2) end do;
%Y Cf. A083374, A143945.
%K nonn,tabf
%O 2,1
%A _Emeric Deutsch_, Sep 19 2008
|
