A180568 - OEIS

%I #7 Feb 16 2025 08:33:13

%S 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,

%T 32,46,44,35,26,17,8,2,37,54,53,44,35,26,17,8,2,42,62,62,53,44,35,26,

%U 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

%N 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.

%C Row n contains n+1 entries.

%C Sum of entries in row n = (3/2)n(3n-1)=A062741(n).

%C The entries in row n are the coefficients of the Wiener polynomial of the grid P_3 x P_n.

%C 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.

%C The average of all distances in the grid P_3 x P_n is (n+3)/3.

%H B. E. Sagan, Y-N. Yeh and P. Zhang, <a href="http://users.math.msu.edu/users/sagan/Papers/Old/wpg-pub.pdf">The Wiener Polynomial of a Graph</a>, Internat. J. of Quantum Chem., 60, 1996, 959-969.

%H Eric Weisstein's World of Mathematics, <a href="https://mathworld.wolfram.com/GridGraph.html">Grid Graph</a>.

%F 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).

%F 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.

%F 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].

%e 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.

%e Triangle starts:

%e 2,1;

%e 7,6,2;

%e 12,14,8,2;

%e 17,22,17,8,2;

%p 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

%Y Cf. A180569

%K nonn,tabf,changed

%O 1,1

%A _Emeric Deutsch_, Sep 28 2010