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
soln by Steven Lord)
Very nice job, Steve. I can help you over the last hurdle going from your summation of f(n) and s(n) to the finite recursion f(n).
s(n) eventually reduces to a cyclic sequence of period 3. So that motivates me to compare f(n) and f(n-3) when expanded:
f(n) = f(n-1) + 2*f(n-2) + 5*f(n-3) + 2*f(n-4) + 2*f(n-5) + 4*f(n-6) + 2*f(n-7) + 2*f(n-8) + 4*f(n-9) + ....
f(n-3) = f(n-4) + 2*f(n-5) + 5*f(n-6) + 2*f(n-7) + 2*f(n-8) + 4*f(n-9) + ....
Now it is easy to see that the expansions for f(n) and f(n-3) are identical for terms f(n-7) and later. Then subtracting the two series will have the long tails cancel each other.
f(n)-f(n-3) = [f(n-1) + 2*f(n-2) + 5*f(n-3) + 2*f(n-4) + 2*f(n-5) + 4*f(n-6)] - [f(n-4) + 2*f(n-5) + 5*f(n-6)]
Now just some basic simplification and we get f(n) = f(n-1) + 2*f(n-2) + 6*f(n-3) + f(n-4) - f(n-6)
re: soln
