|
|
A333476
|
|
Triangle read by rows: T(n,k) gives the number of ways to partition an n X k grid into rectangles of integer side lengths with 0 <= k <= n.
|
|
4
|
|
|
1, 1, 1, 1, 2, 8, 1, 4, 34, 322, 1, 8, 148, 3164, 70878, 1, 16, 650, 31484, 1613060, 84231996, 1, 32, 2864, 314662, 36911922, 4427635270, 535236230270, 1, 64, 12634, 3149674, 846280548, 233276449488, 64878517290010, 18100579400986674
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
0,5
|
|
LINKS
|
|
|
FORMULA
|
|
|
EXAMPLE
|
Triangle begins:
n\k| 0 1 2 3 4 5 6
---+--------------------------------------------------------
0| 1;
1| 1, 1;
2| 1, 2, 8;
3| 1, 4, 34, 322;
4| 1, 8, 148, 3164, 70878;
5| 1, 16, 650, 31484, 1613060, 84231996;
6| 1, 32, 2864, 314662, 36911922, 4427635270, 535236230270;
...
|
|
MAPLE
|
M:= proc(n) option remember; local k; k:= 2^(n-2);
`if`(n=1, Matrix([2]), Matrix(2*k, (i, j)->`if`(i<=k,
`if`(j<=k, M(n-1)[i, j], B(n-1)[i, j-k]),
`if`(j<=k, B(n-1)[i-k, j], 2*M(n-1)[i-k, j-k]))))
end:
B:= proc(n) option remember; local k; k:=2^(n-2);
`if`(n=1, Matrix([1]), Matrix(2*k, (i, j)->`if`(i<=k,
`if`(j<=k, B(n-1)[i, j], B(n-1)[i, j-k]),
`if`(j<=k, B(n-1)[i-k, j], M(n-1)[i-k, j-k]))))
end:
T:= proc(n, m) option remember; `if`((s-> 0 in s or s={1})(
{n, m}), 1, `if`(m>n, T(m, n), add(i, i=map(rhs,
[op(op(2, M(m)^(n-1)))]))))
end:
|
|
MATHEMATICA
|
M[n_] := M[n] = Module[{k = 2^(n - 2)}, If[n == 1, {{2}}, Table[If[i <= k, If[j <= k, M[n - 1][[i, j]], B[n - 1][[i, j - k]]], If[j <= k, B[n - 1][[i - k, j]], 2 M[n - 1][[i - k, j - k]]]], {i, 1, 2k}, {j, 1, 2k}]]];
B[n_] := B[n] = Module[{k = 2^(n - 2)}, If[n == 1, {{1}}, Table[If[i <= k, If[j <= k, B[n - 1][[i, j]], B[n - 1][[i, j - k]]], If[j <= k, B[n - 1][[i - k, j]], M[n - 1][[i - k, j - k]]]], {i, 1, 2k}, {j, 1, 2k}]]];
T[_, 0] = 1;
T[n_, k_] /; k > n := T[k, n];
T[n_, k_] := MatrixPower[M[k], n-1] // Flatten // Total;
|
|
CROSSREFS
|
Columns 0-10 are given by: A000012, A011782, A034999, A208215, A220297, A220298, A220299, A220300, A220301, A220302, A220303.
|
|
KEYWORD
|
|
|
AUTHOR
|
|
|
STATUS
|
approved
|
|
|
|