A361221 Triangle read by rows: T(n,k) is the maximum number of ways in which a set of integer-sided rectangular pieces can tile an n X k rectangle, up to rotations and reflections.
1, 1, 1, 1, 5, 8, 2, 12, 95, 719, 2, 31, 682, 20600, 315107
Offset: 1
Examples
Triangle begins:
n\k| 1 2 3 4 5
---+------------------------
1 | 1
2 | 1 1
3 | 1 5 8
4 | 2 12 95 719
5 | 2 31 682 20600 315107
A 3 X 3 square can be tiled by one 1 X 3 piece, two 1 X 2 pieces and two 1 X 1 pieces in the following 8 ways:
+---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | |
+---+---+ + +---+---+---+ +---+---+---+
| | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+
| | | | | |
+---+---+---+ +---+---+---+ +---+---+---+
.
+---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | |
+ + +---+ + +---+ + + +---+---+
| | | | | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+
| | | | | |
+---+---+---+ +---+---+---+ +---+---+---+
.
+---+---+---+ +---+---+---+
| | | | | |
+---+---+---+ +---+---+---+
| | | |
+---+---+---+ +---+---+---+
| | | | | |
+---+---+---+ +---+---+---+
This is the maximum for a 3 X 3 square, so T(3,3) = 8. There is one other set of pieces that also can tile the 3 X 3 square in 8 ways: three 1 X 2 pieces and three 1 X 1 pieces (see illustration in A361216).
The following table shows all sets of pieces that give the maximum number of tilings for 1 <= k <= n <= 5:
\ Number of pieces of size
(n,k)\ 1 X 1 | 1 X 2 | 1 X 3 | 2 X 2
------+-------+-------+-------+------
(1,1) | 1 | 0 | 0 | 0
(2,1) | 2 | 0 | 0 | 0
(2,1) | 0 | 1 | 0 | 0
(2,2) | 4 | 0 | 0 | 0
(2,2) | 2 | 1 | 0 | 0
(2,2) | 0 | 2 | 0 | 0
(2,2) | 0 | 0 | 0 | 1
(3,1) | 3 | 0 | 0 | 0
(3,1) | 1 | 1 | 0 | 0
(3,1) | 0 | 0 | 1 | 0
(3,2) | 2 | 2 | 0 | 0
(3,3) | 3 | 3 | 0 | 0
(3,3) | 2 | 2 | 1 | 0
(4,1) | 2 | 1 | 0 | 0
(4,2) | 4 | 2 | 0 | 0
(4,3) | 3 | 3 | 1 | 0
(4,4) | 5 | 4 | 1 | 0
(5,1) | 3 | 1 | 0 | 0
(5,1) | 2 | 0 | 1 | 0
(5,1) | 1 | 2 | 0 | 0
(5,2) | 4 | 3 | 0 | 0
(5,3) | 4 | 4 | 1 | 0
(5,4) | 7 | 5 | 1 | 0
(5,5) | 7 | 6 | 2 | 0
It seems that all optimal solutions for A361216 are also optimal here, but occasionally there are other optimal solutions, e.g. for n = k = 3.
Comments