|
%I #53 Mar 15 2023 20:04:35
%S 1,2,2,4,8,4,8,34,34,8,16,148,322,148,16,32,650,3164,3164,650,32,64,
%T 2864,31484,70878,31484,2864,64,128,12634,314662,1613060,1613060,
%U 314662,12634,128,256,55756,3149674,36911922,84231996,36911922,3149674,55756,256
%N Array read by antidiagonals: number of ways of dividing an n X m rectangle into integer-sided rectangles.
%H Alois P. Heinz, <a href="/A116694/b116694.txt">Antidiagonals n = 1..20, flattened</a>
%H 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 Joshua Smith and Helena Verrill, <a href="/A116694/a116694.pdf">On dividing rectangles into rectangles</a>
%e Array begins:
%e 1, 2, 4, 8, 16, 32, ...
%e 2, 8, 34, 148, 650, 2864, ...
%e 4, 34, 322, 3164, 31484, 314662, ...
%e 8, 148, 3164, 70878, 1613060, 36911922, ...
%e 16, 650, 31484, 1613060, 84231996, 4427635270, ...
%e 32, 2864, 314662, 36911922, 4427635270, 535236230270, ...
%p M:= proc(n) option remember; local k; k:= 2^(n-2);
%p `if`(n=1, Matrix([2]), Matrix(2*k, (i, j)->`if`(i<=k,
%p `if`(j<=k, M(n-1)[i, j], B(n-1)[i, j-k]),
%p `if`(j<=k, B(n-1)[i-k, j], 2*M(n-1)[i-k, j-k]))))
%p end:
%p B:= proc(n) option remember; local k; k:=2^(n-2);
%p `if`(n=1, Matrix([1]), Matrix(2*k, (i,j)->`if`(i<=k,
%p `if`(j<=k, B(n-1)[i, j], B(n-1)[i, j-k]),
%p `if`(j<=k, B(n-1)[i-k, j], M(n-1)[i-k, j-k]))))
%p end:
%p A:= proc(n, m) option remember; `if`(n=0 or m=0, 1, `if`(m>n, A(m, n),
%p add(i, i=map(rhs, [op(op(2, M(m)^(n-1)))]))))
%p end:
%p seq(seq(A(n, 1+d-n), n=1..d), d=1..12); # _Alois P. Heinz_, Dec 13 2012
%t 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_ *)
%o (PARI) A116694(m,n)=#fill(m,n) \\ where fill() below computes all tilings. - _M. F. Hasler_, Jan 22 2018
%o 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}
%Y Columns (or rows) 1-10 give: A011782, A034999, A208215, A220297, A220298, A220299, A220300, A220301, A220302, A220303.
%Y Main diagonal gives A182275.
%Y For irreducible or "tight" pavings, see also A285357.
%Y Triangular version: A333476.
%Y A(2n,n) gives A333495.
%K nonn,tabl
%O 1,2
%A Helena Verrill (verrill(AT)math.lsu.edu), Feb 23 2006
%E Edited and more terms from _Alois P. Heinz_, Dec 09 2012
|
