A116694 Array read by antidiagonals: number of ways of dividing an n X m rectangle into integer-sided rectangles.
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
Examples
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, ...
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
Crossrefs
Programs
-
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 *) -
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
Extensions
Edited and more terms from Alois P. Heinz, Dec 09 2012