login
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
OFFSET
1,2
LINKS
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
Columns (or rows) 1-10 give: A011782, A034999, A208215, A220297, A220298, A220299, A220300, A220301, A220302, A220303.
Main diagonal gives A182275.
For irreducible or "tight" pavings, see also A285357.
Triangular version: A333476.
A(2n,n) gives A333495.
Sequence in context: A300182 A317532 A222659 * A220810 A221024 A220545
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