login
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.
1
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).
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
Sequence in context: A094581 A040080 A272033 * A098289 A152020 A055516
KEYWORD
nonn,easy,tabl
AUTHOR
Evan Robinson, Oct 15 2022
STATUS
approved