A356356 Triangle of number of rectangles in the interior of the rectangle with vertices (k,0), (0,k), (n,n+k) and (n+k,n), read by rows.

0, 1, 9, 2, 19, 51, 3, 29, 86, 166, 4, 39, 121, 250, 410, 5, 49, 156, 334, 575, 855, 6, 59, 191, 418, 740, 1141, 1589, 7, 69, 226, 502, 905, 1427, 2044, 2716, 8, 79, 261, 586, 1070, 1713, 2499, 3396, 4356, 9, 89, 296, 670, 1235, 1999, 2954, 4076, 5325, 6645

Offset

1,3

Comments

The function of the triangle T(n,k), where n,k > 0, is equal to (n-k+1)*A330805(k-1) - (n-k)*T(k,k-1) + k*(n-k). This is equivalent to saying that this function is (n-k+1) Aztec diamonds (A330805(k-1)) minus the overlaps of those diamonds (two Aztec diamonds of size k-1 overlapped, hence f(k,k-1)) plus (n-k) copies of k extra rectangles. For this last part, the rectangles are of sizes 1 X (2k-1), 3 X (2k-3), 5 X (2k-5), ..., (2k-3) X 3, (2k-1) X 1 and there are (n-k) copies per overlap.

T(n,n) = A330805(n-1).

If n or k <= 0, T(n,k) = 0.

T(n,k) = T(k,k) + (n-k)*A000447(k). That is, incrementing n for fixed k adds a fixed number of new rectangles, equal to A000447(k).

This sequence was prompted by the codegolf.se question linked below, where the problem was to find T(n,k) plus the number of squares and rectangles in an n X k rectangular lattice with diagonals (lines y+a=+-x).

Links

Evan Robinson, First 100 rows, flattened

Code Golf Stack Exchange, Related problem of finding the number of squares on a diagonal grid

Formula

T(n,k) = (n-k+1)*A330805(k-1) - (n-k)*T(k,k-1) + k*(n-k).

T(n,k) = (n-k+1)*(4*k^4-k^2-3*k)/6 - (n-k)*T(k,k-1) + k*(n-k).

T(n,k) = 1/3*(n-k)*(4*k^3-k) + (4*k^4-k^2-3*k)/6.

T(n,k) = (n-k)*A000447(k) + A330805(k-1).

T(n,1) = n-1.

T(n,n) = A330805(n-1).

T(n,n-1) = (4*n^4-8*n^3-n^2+5*n)/6.

T(n,k) = (n-1)*A000447(k) - T(k,k-1).

Example

Triangle T(n,k) begins:
  n\k  1    2    3    4    5    6    7    8    9   10
   1   0
   2   1    9
   3   2   19   51
   4   3   29   86  166
   5   4   39  121  250  410
   6   5   49  156  334  575  855
   7   6   59  191  418  740 1141 1589
   8   7   69  226  502  905 1427 2044 2716
   9   8   79  261  586 1070 1713 2499 3396 4356
  10   9   89  296  670 1235 1999 2954 4076 5325 6645
For n = 7, k = 3, T(n,k) = (7-3+1)*A330805(3-1) - (7-3)*f(3,2) + 3*(7-3) = 5*51 - 4*19 + 3*4 = 191.

Prog

(Julia)
function T(n, k)
    (2*(n-k)*(4*k^3-k)+(4*k^4-k^2-3*k))÷6
end

Crossrefs

Cf. A330805, A000447.

Sequence in context: A094581 A040080 A272033 * A098289 A152020 A055516

Adjacent sequences: A356353 A356354 A356355 * A356357 A356358 A356359

Keyword

nonn,easy,tabl

Author

Evan Robinson, Oct 15 2022

Status

approved