cp's OEIS Frontend

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.

%I A333476 #40 Mar 16 2023 13:45:00
%S A333476 1,1,1,1,2,8,1,4,34,322,1,8,148,3164,70878,1,16,650,31484,1613060,
%T A333476 84231996,1,32,2864,314662,36911922,4427635270,535236230270,1,64,
%U A333476 12634,3149674,846280548,233276449488,64878517290010,18100579400986674
%N 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.
%H A333476 Alois P. Heinz, <a href="/A333476/b333476.txt">Rows n = 0..12, flattened</a>
%H A333476 David A. Klarner and Spyros S. Magliveras, <a href="https://doi.org/10.1016/S0195-6698(88)80062-3">The number of tilings of a block with blocks</a>, European Journal of Combinatorics 9 (1988), 317-330.
%H A333476 Joshua Smith and Helena Verrill, <a href="/A116694/a116694.pdf">On dividing rectangles into rectangles</a>
%F A333476 T(n,k) = A116694(n,k).
%e A333476 Triangle begins:
%e A333476 n\k| 0   1     2       3         4           5             6
%e A333476 ---+--------------------------------------------------------
%e A333476   0| 1;
%e A333476   1| 1,  1;
%e A333476   2| 1,  2,    8;
%e A333476   3| 1,  4,   34,    322;
%e A333476   4| 1,  8,  148,   3164,    70878;
%e A333476   5| 1, 16,  650,  31484,  1613060,   84231996;
%e A333476   6| 1, 32, 2864, 314662, 36911922, 4427635270, 535236230270;
%e A333476      ...
%p A333476 M:= proc(n) option remember; local k; k:= 2^(n-2);
%p A333476       `if`(n=1, Matrix([2]), Matrix(2*k, (i, j)->`if`(i<=k,
%p A333476       `if`(j<=k, M(n-1)[i, j], B(n-1)[i, j-k]),
%p A333476       `if`(j<=k, B(n-1)[i-k, j], 2*M(n-1)[i-k, j-k]))))
%p A333476     end:
%p A333476 B:= proc(n) option remember; local k; k:=2^(n-2);
%p A333476       `if`(n=1, Matrix([1]), Matrix(2*k, (i, j)->`if`(i<=k,
%p A333476       `if`(j<=k, B(n-1)[i, j], B(n-1)[i, j-k]),
%p A333476       `if`(j<=k, B(n-1)[i-k, j], M(n-1)[i-k, j-k]))))
%p A333476     end:
%p A333476 T:= proc(n, m) option remember; `if`((s-> 0 in s or s={1})(
%p A333476       {n, m}), 1, `if`(m>n, T(m, n), add(i, i=map(rhs,
%p A333476        [op(op(2, M(m)^(n-1)))]))))
%p A333476     end:
%p A333476 seq(seq(T(n, k), k=0..n), n=0..8);  # _Alois P. Heinz_, Mar 23 2020
%t A333476 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}]]];
%t A333476 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 A333476 T[_, 0] = 1;
%t A333476 T[n_, k_] /; k > n := T[k, n];
%t A333476 T[n_, k_] := MatrixPower[M[k], n-1] // Flatten // Total;
%t A333476 Table[Table[T[n, k], {k, 0, n}], {n, 0, 8}] // Flatten (* _Jean-François Alcover_, Nov 23 2020, after _Alois P. Heinz_ *)
%Y A333476 Triangular version of A116694.
%Y A333476 Columns 0-10 are given by: A000012, A011782, A034999, A208215, A220297, A220298, A220299, A220300, A220301, A220302, A220303.
%Y A333476 Main diagonal is given by A182275.
%Y A333476 T(2n,n) gives A333495.
%K A333476 nonn,tabl
%O A333476 0,5
%A A333476 _Peter Kagey_, Mar 23 2020