A113751 Number of diagonal rectangles with corners on an n X n grid of points.

0, 0, 1, 8, 30, 88, 199, 408, 748, 1280, 2053, 3168, 4666, 6712, 9363, 12728, 16952, 22256, 28681, 36536, 45870, 56936, 69967, 85264, 102860, 123232, 146557, 173128, 203138, 237192, 275243, 318104, 365856, 418912, 477649, 542392, 613406, 691848

Offset: 1

Author

T. D. Noe, Nov 09 2005

Keywords

• nonn

Comments

The diagonal rectangles are the ones whose sides are not parallel to the grid axes. All the rectangles can be reflected so that the slope of one side is >= 1. There are a total of A046657(n-1) these slopes. These slopes are the basis of the Mathematica program that counts the rectangles.

Examples

			a(3) = 1 because for the 3 X 3 grid, there is only one diagonal rectangle - a square having sides sqrt(2) units.
a(4) = 8 because for the 4 X 4 grid, there are 4 squares having sides sqrt(2) units, 2 squares having sides sqrt(5) units and 2 rectangles that are sqrt(2) by 2*sqrt(2) units.
		

Links

• Jinyuan Wang, Table of n, a(n) for n = 1..1000

Crossrefs

Cf. A000537 (parallel rectangles on an n X n grid), A085582 (all rectangles on an n X n grid).

Programs

Mathematica

Table[n=m-1; slopes=Union[Flatten[Table[a/b, {b, n}, {a, b, n-b}]]]; rects=0; Do[b=Numerator[slopes[[i]]]; a=Denominator[slopes[[i]]]; base={a+b, a+b}; l=0; While[l++; k=l; While[extent=base+{b, a}(k-1)+{a, b}(l-1); extent[[1]]<=n && extent[[2]]<=n, pos={n+1, n+1}-extent; If[a==b && k==l, fact=1, If[pos[[1]]==pos[[2]], fact=2, fact=4]]; rects=rects+fact*Times@@pos; k++ ]; k>l], {i, Length[slopes]}]; rects, {m, 1, 42}]

Formula

a(n) = A085582(n) - A000537(n-1). [corrected by David Radcliffe, Feb 06 2020]

Extensions

a(1) = 0 prepended by Jinyuan Wang, Feb 06 2020