cp's OEIS Frontend

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.

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