A116694
Array read by antidiagonals: number of ways of dividing an n X m rectangle into integer-sided rectangles.
Original entry on oeis.org
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
Helena Verrill (verrill(AT)math.lsu.edu), Feb 23 2006
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, ...
For irreducible or "tight" pavings, see also
A285357.
-
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
-
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 *)
-
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
A360499
Number of ways to tile an n X n square using rectangles with distinct dimensions.
Original entry on oeis.org
1, 1, 21, 269, 4489, 82981, 2995185, 118897973
Offset: 1
a(1) = 1 as the only way to tile a 1 x 1 square is with a square with dimensions 1 x 1.
a(2) = 1 as the only way to tile a 2 x 2 square is with a square with dimensions 2 x 2.
a(3) = 21. The possible tilings, excluding those equivalent by symmetry, are:
.
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | |
+ + +---+---+---+ +---+---+ + +---+---+---+
| | | | | | | | |
+ + + + + + + + +
| | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
.
The first tiling can occur in 1 way, the second in 8 different ways, the third in 8 different ways and the fourth in 4 different ways, giving 21 ways in total.
A360256
Number of ways to tile an n X n square using rectangles with distinct height X width dimensions.
Original entry on oeis.org
1, 1, 33, 513, 14409, 693025, 50447161
Offset: 1
a(1) = 1 as the only way to tile a 1 X 1 square is with a square with dimensions 1 X 1.
a(2) = 1 as the only way to tile a 2 X 2 square is with a square with dimensions 2 X 2.
a(3) = 33. The possible tilings, excluding those equivalent by symmetry, are:
.
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+ + +---+---+---+ +---+---+---+
| | | | | | | | | | | | |
+ + + + + + + + + + + + +
| | | | | | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+ +---+---+---+
.
The first tiling can occur in 4 different ways, the second in 8 different ways, the third in 8 different ways, the fourth in 4 different ways and the fifth in 8 different ways. There is also the single 3 X 3 rectangle. This gives 33 ways in total.
A333476
Triangle read by rows: T(n,k) gives the number of ways to partition an n X k grid into rectangles of integer side lengths with 0 <= k <= n.
Original entry on oeis.org
1, 1, 1, 1, 2, 8, 1, 4, 34, 322, 1, 8, 148, 3164, 70878, 1, 16, 650, 31484, 1613060, 84231996, 1, 32, 2864, 314662, 36911922, 4427635270, 535236230270, 1, 64, 12634, 3149674, 846280548, 233276449488, 64878517290010, 18100579400986674
Offset: 0
Triangle begins:
n\k| 0 1 2 3 4 5 6
---+--------------------------------------------------------
0| 1;
1| 1, 1;
2| 1, 2, 8;
3| 1, 4, 34, 322;
4| 1, 8, 148, 3164, 70878;
5| 1, 16, 650, 31484, 1613060, 84231996;
6| 1, 32, 2864, 314662, 36911922, 4427635270, 535236230270;
...
Columns 0-10 are given by:
A000012,
A011782,
A034999,
A208215,
A220297,
A220298,
A220299,
A220300,
A220301,
A220302,
A220303.
-
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:
T:= proc(n, m) option remember; `if`((s-> 0 in s or s={1})(
{n, m}), 1, `if`(m>n, T(m, n), add(i, i=map(rhs,
[op(op(2, M(m)^(n-1)))]))))
end:
seq(seq(T(n, k), k=0..n), n=0..8); # Alois P. Heinz, Mar 23 2020
-
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}]]];
T[_, 0] = 1;
T[n_, k_] /; k > n := T[k, n];
T[n_, k_] := MatrixPower[M[k], n-1] // Flatten // Total;
Table[Table[T[n, k], {k, 0, n}], {n, 0, 8}] // Flatten (* Jean-François Alcover, Nov 23 2020, after Alois P. Heinz *)
A208215
Number of ways of dividing a 3 X n rectangle into rectangles of integer side lengths.
Original entry on oeis.org
1, 4, 34, 322, 3164, 31484, 314662, 3149674, 31544384, 315981452, 3165414034, 31710994234, 317682195692, 3182564368244, 31883205466534, 319408833724882, 3199866987994304, 32056562443839284, 321145602837871522, 3217266324544621714, 32230871396722195484
Offset: 0
For n=1 the a(1) = 4 ways to divide are:
._ _ _ _
|_| |_| | | | |
|_| | | |_| | |
|_| |_| |_| |_|
-
Join[{1}, LinearRecurrence[{15, -55, 51}, {4, 34, 322}, 20]] (* Bruno Berselli, Apr 24 2012 *)
A360725
Number of ways to tile an n X n square using oblongs with distinct height x width dimensions.
Original entry on oeis.org
0, 0, 4, 36, 1056, 31052, 1473944, 87469884
Offset: 1
a(1) = 0 as no distinct oblongs can tile a square with dimensions 1 x 1.
a(2) = 0 as no distinct oblongs can tile a square with dimensions 2 x 2.
a(3) = 4. There is one tiling, excluding those equivalent by symmetry:
.
+---+---+---+
| |
+---+---+---+
| |
+ +
| |
+---+---+---+
.
This tiling can occur in 4 different ways, giving 4 ways in total.
a(4) = 36. The possible tilings, excluding those equivalent by symmetry, are:
.
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+ +---+---+---+---+
| | | | | | | | | | |
+ + + +---+---+---+---+ + +---+---+---+ + +---+---+---+
| | | | | | | | | | | |
+---+---+---+---+ + + + + + + + + +
| | | | | | | | | | |
+ + + + +---+---+---+---+ +---+---+ +
| | | | | | | | |
+---+---+---+---+ +---+---+---+---+ +---+---+---+---+ +---+---+---+---+
.
The first tiling can occur in 8 different ways, the second in 4 different ways, the third in 16 different ways and the fourth in 8 different ways. This gives 36 ways in total.
A360773
Number of ways to tile a 2n X 2n square using rectangles with distinct dimensions such that the sum of the rectangles perimeters equals the area of the square.
Original entry on oeis.org
0, 1, 8, 1024, 620448
Offset: 1
a(1) = 0 as a 2 x 2 square, with area 4, cannot be tiled with distinct rectangles with perimeters that sum to 4.
a(2) = 1 as a 4 x 4 rectangle, with area 16, can be tiled with a 4 x 4 square with perimeter 4 + 4 + 4 + 4 = 16.
a(3) = 8. The possible tilings for the 6 x 6 square, with area 36, excluding those equivalent by symmetry, are:
.
+---+---+---+---+---+---+ +---+---+---+---+---+---+
| | | |
+---+---+---+---+---+---+ + +
| | | |
+ + +---+---+---+---+---+---+
| | | |
+ + + +
| | | |
+ + + +
| | | |
+ + + +
| | | |
+---+---+---+---+---+---+ +---+---+---+---+---+---+
.
where for the first tiling (2*6 + 2*1) + (2*6 + 2*5) = 36 while for the second tiling (2*6 + 2*2) + (2*6 + 2*4) = 36. Both of these tilings can occur in 4 ways, giving 8 ways in total.
a(4) = 1024. And example tiling of the 8 x 8 square, with area 64, is:
.
+---+---+---+---+---+---+---+---+
| | | |
+ + +---+---+
| | | |
+ + + +
| | | |
+---+---+---+---+---+---+---+---+
| |
+ +
| |
+ +
| |
+ +
| |
+ +
| |
+---+---+---+---+---+---+---+---+
.
where (2*1 + 2*3) + (2*5 + 2*3) + (2*2 + 2*1) + (2*2 + 2*2) + (2*8 + 2*5) = 64.
A360804
Number of ways to tile an n X n square using rectangles with distinct areas.
Original entry on oeis.org
1, 1, 21, 253, 2401, 36237, 815929, 18713197
Offset: 1
a(1) = 1 as the only way to tile a 1 X 1 square is with a square with dimensions 1 X 1.
a(2) = 1 as the only way to tile a 2 X 2 square is with a square with dimensions 2 X 2.
a(3) = 21. The possible tilings are the same as those given in the examples of A360499(3).
a(4) = 253. And example tiling of the 4 X 4 square is:
.
+---+---+---+---+
| | | |
+---+---+---+ +
| | |
+ + +
| | |
+---+---+---+---+
| |
+---+---+---+---+
.
which contains rectangles with areas 1, 2, 3, 4, 6. The one tiling, excluding symmetrically equivalent arrangements, that is excluded here but allowed in A360499 is:
.
+---+---+---+---+
| | |
+ + +
| | |
+---+---+ +
| | |
+---+---+---+---+
| |
+---+---+---+---+
.
as this contains two rectangles with area 4. This can occur in 16 different ways so a(4) = A360499(4) - 16 = 269 - 16 = 253.
A361524
Number of ways of dividing an n X n square into integer-sided rectangles, up to rotations and reflections.
Original entry on oeis.org
1, 1, 4, 54, 9235, 10538496, 66906507915, 2262572656817797, 406359897582963166777, 387240433077951047222490766, 1957233446631303872408683778546809, 52459774417987065589052845904624173777442, 7455958280198359250316552005822713102696893557376
Offset: 0
A360943
Number of ways to tile an n X n square using rectangles with distinct dimensions where no rectangle has an edge length that divides n.
Original entry on oeis.org
0, 0, 0, 0, 0, 0, 360, 0, 360, 360, 8547192, 0
Offset: 1
a(1)..a(6),a(8),a(12) = 0 as these squares cannot be tiled with distinct rectangles with edge lengths that do not divide n. For example for the 8 x 8 square only three rectangles are available with dimensions 3 x 3, 3 x 5, and 5 x 5. All other rectangles have an edge length that divides 8 else leave a space of size 1 or 2 units between its edge and the edge of the square. These gaps cannot be filled as no rectangle can have an edge length of 1 or 2.
a(7) = 360. And example tiling is:
.
+---+---+---+---+---+---+---+
| | | |
+ + + +
| | | |
+---+---+---+---+---+ +
| | |
+ + +
| | |
+---+---+---+---+---+---+---+
| | |
+ + +
| | |
+ + +
| | |
+---+---+---+---+---+---+---+
.
Showing 1-10 of 11 results.
Comments