login
The OEIS Foundation is supported by donations from users of the OEIS and by a grant from the Simons Foundation.

 

Logo

Thanks to everyone who made a donation during our annual appeal!
To see the list of donors, or make a donation, see the OEIS Foundation home page.

Hints
(Greetings from The On-Line Encyclopedia of Integer Sequences!)
A116694 Array read by antidiagonals: number of ways of dividing an n X m rectangle into integer sided rectangles. 15

%I

%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 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 Diagonal gives: A182275.

%Y For irreducible or "tight" pavings, see also A285357.

%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

Lookup | Welcome | Wiki | Register | Music | Plot 2 | Demos | Index | Browse | More | WebCam
Contribute new seq. or comment | Format | Style Sheet | Transforms | Superseeker | Recent
The OEIS Community | Maintained by The OEIS Foundation Inc.

License Agreements, Terms of Use, Privacy Policy. .

Last modified January 18 16:27 EST 2020. Contains 331011 sequences. (Running on oeis4.)