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

Author

Helena Verrill (verrill(AT)math.lsu.edu), Feb 23 2006

Keywords

• nonn
• tabl

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

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.

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