A289832 Triangle read by rows: T(n,k) = number of rectangles all of whose vertices lie on an (n+1) X (k+1) rectangular grid.

1, 3, 10, 6, 20, 44, 10, 33, 74, 130, 15, 49, 110, 198, 313, 21, 68, 152, 276, 443, 640, 28, 90, 200, 364, 592, 866, 1192, 36, 115, 254, 462, 756, 1113, 1550, 2044, 45, 143, 314, 570, 935, 1385, 1944, 2586, 3305, 55, 174, 380, 688, 1129, 1680, 2370, 3172, 4081, 5078

Offset: 1

Author

Hector J. Partridge, Jul 13 2017

Keywords

• nonn
• tabl

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.

Examples

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

Crossrefs

Cf. A000217, A085582, A140229, A096948.

Programs

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']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)