A085582 The number of rectangles (orthogonal or not) with corners on an n X n grid of points.

0, 1, 10, 44, 130, 313, 640, 1192, 2044, 3305, 5078, 7524, 10750, 14993, 20388, 27128, 35448, 45665, 57922, 72636, 89970, 110297, 133976, 161440, 192860, 228857, 269758, 316012, 367974, 426417, 491468, 564120, 644640, 733633, 831674, 939292

Offset: 1

Author

Yuval Dekel (dekelyuval(AT)hotmail.com), Jul 06 2003

Keywords

• nonn

Examples

			a(3) = 10 because on the 3 X 3 grid there are four 1 X 1 rectangles, two 1 X 2s, two 2 X 1's, one 2 X 2 and one 45-degree rectangle, sqrt(2) X sqrt(2).
		

Links

• David Radcliffe, Table of n, a(n) for n = 1..1000
• David Radcliffe, Python script to calculate a(n)

Crossrefs

Cf. A000537, A002415, A113751 (diagonal rectangles on an n X n grid).

Formula

a(n) = A000537(n-1) + A113751(n). - T. D. Noe, Nov 09 2005 [corrected by David Radcliffe, Feb 06 2020]

a(n) = n*(n-1)^2*(2n-1)/6 + 2*Sum_{a,b>0, 0David Radcliffe, Feb 06 2020

Extensions

Edited by Don Reble, Nov 05 2005