There are two triominoes. One is simple a 1x3 rectangle and the other is a small
L-shaped piece.
Using any combination of these two triominoes and in any orientation, how many ways can a 3 by N rectangle be tiled?
Rotations and reflections of an asymmetrical solution are to be considered distinct.
(In reply to
thanks by Steven Lord)
I haven't tried to read the paper you cited, but I do have my own proof that our building blocks are the 2 oddballs and 3 infinite sets.
First let's make our blocks out of only the straight triomino. A single vertical piece has a fault line on each side. So a vertical piece by itself is a block.
The other option is placing the pieces horizontally, then we need to start all three pieces at the same edge. (we don't have the L-piece available) So then we get a 3x3 square of three horizontal pieces stacked on each other - and again we have a fault line on either side. So this is our second block; and that is all the blocks we can make with just the straight triomino.
So now let's move on to adding the L-triomino. Consider this diagram:
.AB..
..C..
..CC.
The C's represent a placed L-triomino. Assume a single other triomino covers both A and B. But then draw a vertical line at the tall vertical edge of triomino C. This cuts between A and B - so now we have a partial triomino to the left and right of the line.
But the line also splits the rectangle into two smaller rectangles each with area that is a multiple of 3. But since each rectangle has a partial triomino in it we run into a problem since the untiled area is not a multiple of 3.
This is a contradiction. So our assumption of placing a single triomino to cover both A and B is wrong.
This means that every possible placement of a L-triomino is at a fault line in the tiling. Which means that an L-triomino can only occur at the left end or right end of a building block.
Also, we can infer that every block with an L-triomino at one end must have a mate at the other end to match up the parity of the rows. Then at this point we can construct the three infinite families of blocks by choosing how the two L-triominos are placed relative to each other.