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,3

Links

David Radcliffe, Table of n, a(n) for n = 1..1000

David Radcliffe, Python script to calculate a(n)

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, 0<s<r<n, gcd(r,s)=1} max(n-a*s-b*r,0)*max(n-a*r-b*s,0). - David Radcliffe, Feb 06 2020

Example

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

Crossrefs

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

Sequence in context: A256050 A257052 A008532 * A058310 A005720 A060326

Adjacent sequences: A085579 A085580 A085581 * A085583 A085584 A085585

Keyword

nonn

Author

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

Extensions

Edited by Don Reble, Nov 05 2005

Status

approved