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

Links

Table of n, a(n) for n=1..55.

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

Cf. A000217, A085582, A140229, A096948.

Sequence in context: A337275 A087397 A210414 * A196163 A195922 A261836

Adjacent sequences: A289829 A289830 A289831 * A289833 A289834 A289835

Keyword

nonn,tabl

Author

Hector J. Partridge, Jul 13 2017

Status

approved