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

%I #28 Mar 11 2018 14:15:12

%S 1,3,10,6,20,44,10,33,74,130,15,49,110,198,313,21,68,152,276,443,640,

%T 28,90,200,364,592,866,1192,36,115,254,462,756,1113,1550,2044,45,143,

%U 314,570,935,1385,1944,2586,3305,55,174,380,688,1129,1680,2370,3172,4081,5078

%N 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 T(n,k) is the number of rectangles (including squares) that can be drawn on an (n+1) X (k+1) grid.

%C 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 Column k=1 equals A000217.

%C 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 Triangle T(n,k) begins:

%e n/k 1 2 3 4 5 6 7 8 9 10

%e 1 1

%e 2 3 10

%e 3 6 20 44

%e 4 10 33 74 130

%e 5 15 49 110 198 313

%e 6 21 68 152 276 443 640

%e 7 28 90 200 364 592 866 1192

%e 8 36 115 254 462 756 1113 1550 2044

%e 9 45 143 314 570 935 1385 1944 2586 3305

%e 10 55 174 380 688 1129 1680 2370 3172 4081 5078

%e e.g., there are T(3,3) = 44 rectangles in a 4 X 4 lattice:

%e There are A096948(3,3) = 36 rectangles whose sides are parallel to the axes;

%e There are 4 squares with side length sqrt(2);

%e There are 2 squares with side length sqrt(5);

%e There are 2 rectangles with side lengths sqrt(2) X 2 sqrt(2).

%o (Python)

%o from math import gcd

%o def countObliques(a,b,c,d,n,k):

%o if(gcd(a, b) == 1): #avoid double counting

%o boundingBox={'width':(b * c) + (a * d),'height':(a * c) + (b * d)}

%o if(boundingBox['width']<n and boundingBox['height']<k):

%o return (n - boundingBox['width']) * (k - boundingBox['height'])

%o return 0

%o def totalRectangles(n,k):

%o #rectangles parallel to axes: A096948

%o ret=(n*(n-1)*k*(k-1))/4

%o #oblique rectangles

%o ret+=sum(countObliques(a,b,c,d,n,k) for a in range(1,n) \

%o for b in range(1,n) \

%o for c in range(1,k) \

%o for d in range(1,k))

%o return ret

%o Tnk=[[totalRectangles(n+1,k+1) for k in range(1, n+1)] for n in range(1, 20)]

%o print(Tnk)

%Y Cf. A000217, A085582, A140229, A096948.

%K nonn,tabl

%O 1,2

%A _Hector J. Partridge_, Jul 13 2017