A143945 Wiener index of the grid P_n x P_n, where P_n is the path graph on n vertices.

0, 8, 72, 320, 1000, 2520, 5488, 10752, 19440, 33000, 53240, 82368, 123032, 178360, 252000, 348160, 471648, 627912, 823080, 1064000, 1358280, 1714328, 2141392, 2649600, 3250000, 3954600, 4776408, 5729472, 6828920, 8091000, 9533120, 11173888, 13033152, 15132040

Offset

1,2

Comments

The Wiener index of a connected graph is the sum of the distances between all unordered pairs of vertices in the graph.

Links

Vincenzo Librandi, Table of n, a(n) for n = 1..1000 (corrected by Ray Chandler, Jan 19 2019)

Dragan Stevanovic, Hosoya polynomial of composite graphs, Discrete Math., Vol. 235, No. 1-3 (2001), pp. 237-244.

B.-Y. Yang and Y.-N. Yeh, Wiener polynomials of some chemically interesting graphs, International Journal of Quantum Chemistry, Vol. 99 (2004), pp. 80-91.

Y.-N. Yeh and I. Gutman, On the sum of all distances in composite graphs, Discrete Math., Vol. 135, No. 1-3 (1994), pp. 359-365.

Eric Weisstein's World of Mathematics, Grid Graph.

Eric Weisstein's World of Mathematics, Wiener Index.

Index entries for linear recurrences with constant coefficients, signature (6,-15,20,-15,6,-1).

Formula

a(n) = Sum_{k=1..2n-2} k*A143944(n,k).

a(n) = n^3*(n^2-1)/3.

a(n) = 8*A006414(n-2). G.f.: 8*x^2*(1+3*x+x^2)/(x-1)^6. - R. J. Mathar, Sep 15 2010

a(n) = 6*a(n-1)-15*a(n-2)+20*a(n-3)-15*a(n-4)+6*a(n-5)-a(n-6), a(2)=8, a(3)=72, a(4)=320, a(5)=1000, a(6)=2520, a(7)=5488. - Harvey P. Dale, Feb 07 2014

From Amiram Eldar, Jan 09 2022: (Start)

Sum_{n>=2} 1/a(n) = 15/4 - 3*zeta(3).

Sum_{n>=2} (-1)^n/a(n) = 9*zeta(3)/4 + 6*log(2) - 27/4. (End)

Example

a(2)=8 because in P_2 x P_2 (a square) there are 4 distances equal to 1 and 2 distances equal to 2 (4*1 + 2*2 = 8).

Maple

seq((1/3)*n^3*(n^2-1), n=1..33);

Mathematica

Table[n^3 (n^2 - 1)/3, {n, 40}] (* Harvey P. Dale, Feb 07 2014 *)
LinearRecurrence[{6, -15, 20, -15, 6, -1}, {0, 8, 72, 320, 1000, 2520}, 30] (* Harvey P. Dale, Feb 07 2014 *)
CoefficientList[Series[8 x (1 + 3 x + x^2)/(x - 1)^6, {x, 0, 40}], x] (* Vincenzo Librandi, Feb 08 2014 *)

Prog

(Magma) [n^3*(n^2-1)/3: n in [1..40]]; // Vincenzo Librandi, Feb 08 2014
(PARI) a(n)=n^3*(n^2-1)/3 \\ Charles R Greathouse IV, Oct 21 2022

Crossrefs

Main diagonal of A143368.

Cf. A006414, A143944, A245828, A192828.

Sequence in context: A044576 A104453 A254371 * A239095 A189954 A271028

Adjacent sequences: A143942 A143943 A143944 * A143946 A143947 A143948

Keyword

nonn,easy

Author

Emeric Deutsch, Sep 20 2008

Status

approved