|
EXAMPLE
|
Triangle begins:
n\k| 1 2 3 4 5 6 7 8
---+--------------------------------------------------------
1 | 1
2 | 1 4
3 | 2 11 56
4 | 3 29 370 5752
5 | 4 94 2666 82310 2519124
6 | 6 263 19126 1232770 88117873 6126859968
7 | 12 968 134902 19119198 2835424200 ? ?
8 | 20 3416 1026667 307914196 109979838540 ? ? ?
A 3 X 3 square can be tiled by three 1 X 2 pieces and three 1 X 1 pieces in the following ways:
+---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | | | |
+---+---+---+ + +---+---+ +---+ +---+
| | | | | | | | | | |
+---+---+ + +---+---+ + +---+---+ +
| | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+
.
+---+---+---+ +---+---+---+ +---+---+---+
| | | | | | | | | |
+---+---+---+ +---+---+ + +---+---+---+
| | | | | | | | | |
+---+---+ + +---+---+---+ +---+---+---+
| | | | | | | | |
+---+---+---+ +---+---+---+ +---+---+---+
.
+---+---+---+ +---+---+---+
| | | | | |
+---+---+---+ +---+---+---+
| | | | | |
+---+---+---+ +---+---+---+
| | | | | |
+---+---+---+ +---+---+---+
The first six of these have no symmetries, so they account for 8 tilings each. The last two has a mirror symmetry, so they account for 4 tilings each. In total there are 6*8+2*4 = 56 tilings. This is the maximum for a 3 X 3 square, so T(3,3) = 56.
The following table shows the sets of pieces that give the maximum number of tilings up to (n,k) = (7,5). The solutions are unique except for (n,k) = (2,1) and (n,k) = (6,1).
\ Number of pieces of size
(n,k)\ 1 X 1 | 1 X 2 | 1 X 3 | 1 X 4
------+-------+-------+-------+------
(1,1) | 1 | 0 | 0 | 0
(2,1) | 2 | 0 | 0 | 0
(2,1) | 0 | 1 | 0 | 0
(2,2) | 2 | 1 | 0 | 0
(3,1) | 1 | 1 | 0 | 0
(3,2) | 2 | 2 | 0 | 0
(3,3) | 3 | 3 | 0 | 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,2) | 4 | 3 | 0 | 0
(5,3) | 4 | 4 | 1 | 0
(5,4) | 7 | 5 | 1 | 0
(5,5) | 7 | 6 | 2 | 0
(6,1) | 2 | 2 | 0 | 0
(6,1) | 1 | 1 | 1 | 0
(6,2) | 4 | 4 | 0 | 0
(6,3) | 7 | 4 | 1 | 0
(6,4) | 8 | 5 | 2 | 0
(6,5) | 10 | 7 | 2 | 0
(6,6) | 11 | 8 | 3 | 0
(7,1) | 2 | 1 | 1 | 0
(7,2) | 5 | 3 | 1 | 0
(7,3) | 8 | 5 | 1 | 0
(7,4) | 10 | 6 | 2 | 0
(7,5) | 11 | 7 | 2 | 1
|