OFFSET
1,2
LINKS
Alois P. Heinz, Antidiagonals n = 1..20, flattened
David A. Klarner and Spyros S. Magliveras, The number of tilings of a block with blocks, European Journal of Combinatorics 9 (1988), 317-330.
Joshua Smith and Helena Verrill, On dividing rectangles into rectangles
EXAMPLE
Array begins:
1, 2, 4, 8, 16, 32, ...
2, 8, 34, 148, 650, 2864, ...
4, 34, 322, 3164, 31484, 314662, ...
8, 148, 3164, 70878, 1613060, 36911922, ...
16, 650, 31484, 1613060, 84231996, 4427635270, ...
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:
A:= proc(n, m) option remember; `if`(n=0 or m=0, 1, `if`(m>n, A(m, n),
add(i, i=map(rhs, [op(op(2, M(m)^(n-1)))]))))
end:
seq(seq(A(n, 1+d-n), n=1..d), d=1..12); # Alois P. Heinz, Dec 13 2012
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}]]]; A[0, 0] = 1; A[n_ , m_ ] /; m>n := A[m, n]; A[n_ , m_ ] :=MatrixPower[M[m], n-1] // Flatten // Total; Table[Table[A[n, 1+d-n], {n, 1, d}], {d, 1, 12}] // Flatten (* Jean-François Alcover, Feb 23 2015, after Alois P. Heinz *)
PROG
(PARI) A116694(m, n)=#fill(m, n) \\ where fill() below computes all tilings. - M. F. Hasler, Jan 22 2018
fill(m, n, A=matrix(m, n), i=1, X=1, Y=1)={while((Y>n&&X++&&!Y=0)||A[X, Y], X>m&&return([A]); Y++); my(N=n, L=[]); for(x=X, m, A[x, Y]&&break; for(y=Y, N, if(A[x, y], for(j=y, N, for(k=X, x-1, A[k, j]=0)); N=y-1; break); for(j=X, x, A[j, y]=i); L=concat(L, fill(m, n, A, i+1, X, y+1))); x<m&&!A[x+1, Y]&&for(j=Y+1, N, for(i=X, x, A[i, j]=0))); L}
CROSSREFS
KEYWORD
nonn,tabl
AUTHOR
Helena Verrill (verrill(AT)math.lsu.edu), Feb 23 2006
EXTENSIONS
Edited and more terms from Alois P. Heinz, Dec 09 2012
STATUS
approved