How many ways can you tile an NxM rectangle with L-polyominos? I came up with a problem that's been bugging me:
How many ways can you tile an NxM rectangle with L-polyominos?
The L shapes can be any size, so long as they aren't lines.
For clarification:
$L(1,m) = 0$,
$L(2,2) = 0$,
$L(2,3) = 2$,
$L(2,4) = 2$,
$L(3,3) = 0$...
I've tried solving it using recursion (the only way I know how), by dividing the NxM grid into 2 smaller grids, but that doesn't account for many of the possibilities.
Solving the problem algorithmically is pretty easy (I hope :P). Here are some of the values I get:
$
\begin{bmatrix}
0 & 0 & 0 & 0 & 0 & 0 \\[0.3em]
0 & 0 & 2 & 2 & 2 & 6 \\[0.3em]
0 & 2 & 0 & 20 & 64 & 234 \\[0.3em]
0 & 2 & 20 & 110 & 752 & 4522 \\[0.3em]
0 & 2 & 64 & 752 & 7720 & 84846 \\[0.3em]
0 & 6 & 234 & 4522 & 84846 & 1557970
\end{bmatrix}$
I hope that makes sense: L(1,1) is in the top left, and L(6,6) is in the bottom right. Obviously its symmetrical diagonally. 
 A: (EDITED)
For the $2 \times m$ case, it seems to me the recursion is
$$ L(2,m) = 2 \sum_{j=0}^{m-3} L(2,j)$$ where $L(2,0) = 1$, and the
solution to that is 
$$L(2,m) = \sum_r \dfrac{9-3r-2r^2}{29 r^m}$$
the sum being over the three roots $r$ of $2 z^3+z-1$ (approximately
$.58975$ and $-.29488 \pm .87227 i$).
Cases with $N > 2$ are going to be more complicated.  Essentially you 
want to look at all possibilities for what happens at one end of the grid.
But even for $N=3$ there are quite a few possibilities.
A: This is primarily just a reformulation, but one that seems helpful in replacing the global rule (only L-shaped polyominoes) with a local one.  The problem is equivalent to the following:

How many ways can you fill an $M\times N$ grid with these three tiles (rotations and reflections are allowed) if each blue dot must be adjacent to a red dot and vice versa?
 


This formulation can be used to obtain a recursion relation for the number of ways a given row can be filled with specified top and bottom borders, where each border is a list of white, red, and blue edges; i.e., you can derive a $3^M \times 3^M$ transfer matrix.
