OFFSET
1,2
COMMENTS
T(n,k) is the number of rectangles (including squares) that can be drawn on an (n+1) X (k+1) grid.
The diagonal of T(n,k) is the number of rectangles in a square lattice (A085582), i.e., T(n,n) = A085582(n+1).
Column k=1 equals A000217.
Column k=2 equals A140229 for n >= 3 as the only oblique rectangles are squares of side length sqrt(2), leading to the same formula.
EXAMPLE
Triangle T(n,k) begins:
n/k 1 2 3 4 5 6 7 8 9 10
1 1
2 3 10
3 6 20 44
4 10 33 74 130
5 15 49 110 198 313
6 21 68 152 276 443 640
7 28 90 200 364 592 866 1192
8 36 115 254 462 756 1113 1550 2044
9 45 143 314 570 935 1385 1944 2586 3305
10 55 174 380 688 1129 1680 2370 3172 4081 5078
e.g., there are T(3,3) = 44 rectangles in a 4 X 4 lattice:
There are A096948(3,3) = 36 rectangles whose sides are parallel to the axes;
There are 4 squares with side length sqrt(2);
There are 2 squares with side length sqrt(5);
There are 2 rectangles with side lengths sqrt(2) X 2 sqrt(2).
PROG
(Python)
from math import gcd
def countObliques(a, b, c, d, n, k):
if(gcd(a, b) == 1): #avoid double counting
boundingBox={'width':(b * c) + (a * d), 'height':(a * c) + (b * d)}
if(boundingBox['width']<n and boundingBox['height']<k):
return (n - boundingBox['width']) * (k - boundingBox['height'])
return 0
def totalRectangles(n, k):
#rectangles parallel to axes: A096948
ret=(n*(n-1)*k*(k-1))/4
#oblique rectangles
ret+=sum(countObliques(a, b, c, d, n, k) for a in range(1, n) \
for b in range(1, n) \
for c in range(1, k) \
for d in range(1, k))
return ret
Tnk=[[totalRectangles(n+1, k+1) for k in range(1, n+1)] for n in range(1, 20)]
print(Tnk)
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Hector J. Partridge, Jul 13 2017
STATUS
approved