|
|
A116694
|
|
Array read by antidiagonals: number of ways of dividing an n X m rectangle into integer-sided rectangles.
|
|
20
|
|
|
1, 2, 2, 4, 8, 4, 8, 34, 34, 8, 16, 148, 322, 148, 16, 32, 650, 3164, 3164, 650, 32, 64, 2864, 31484, 70878, 31484, 2864, 64, 128, 12634, 314662, 1613060, 1613060, 314662, 12634, 128, 256, 55756, 3149674, 36911922, 84231996, 36911922, 3149674, 55756, 256
(list;
table;
graph;
refs;
listen;
history;
text;
internal format)
|
|
|
OFFSET
|
1,2
|
|
LINKS
|
|
|
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:
|
|
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
|
For irreducible or "tight" pavings, see also A285357.
|
|
KEYWORD
|
|
|
AUTHOR
|
Helena Verrill (verrill(AT)math.lsu.edu), Feb 23 2006
|
|
EXTENSIONS
|
|
|
STATUS
|
approved
|
|
|
|