# 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.

-
(1) Does an $N\times M$-grid have $N\times M$ points or $N\times M$ lines? (2) What precisely is an L-shape? (I could not reversely define it from your given values.) – flonk Feb 18 '14 at 10:54
As in, an N x M grid of dots, where every dot is part of exactly one "L shape". An "L shape" is a horizontal line of dots (H) joined to a vertical line of dots (V) such that one dot on the end of H is also on the end of V, and that |H| >= 2 and |V| >= 2. For further clarification, |H union V| = |V| + |H| - 1 – AStupidNoob Feb 18 '14 at 15:00
I would think that $L(2,2)=2$, with one solution consisting of the two L-shapes $\{(1,0),(0,0),(0,1)\}, \{(1,0),(1,1),(0,1)\}$ and the second solution being the same rotated by $90°$. Where is my mistake? Could you specify more clearly, what is meant by being entirely filled? Are the individual L-shapes allowed to "touch" or "overlap"? In other words: does every dot need to be occupied and are dots allowed to be occupied by multiple L-shapes? – flonk Feb 18 '14 at 20:01
Every dot is part of exactly one "L shape". I.E, they cannot overlap, they are allowed to be adjacent. "Entirely filled" means that there are no dots left in the grid that are not part of an L shape. – AStupidNoob Feb 19 '14 at 1:35
Thanks, got it :) – flonk Feb 19 '14 at 8:28

(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.

-
I thought about maybe trying some kind of recursion where you do it by row. You start with the first row, and fill it with either L end-points or the horizontal part of the L. Then you recurse by filling out the rest of the space with rectangles. Or maybe some kind of crazy algebraic type solution, since we know that every cell is either an endpoint, a "flat" or a corner, and the number of corners is half the number of endpoints. Or something. I really have no idea what I'm doing :) – AStupidNoob Feb 13 '14 at 3:11
The solution differs from the given example values, e.g. $L(2,2)=2\neq 0$. – flonk Feb 19 '14 at 8:31
Oops, thanks for noticing. I fixed it. – Robert Israel Feb 19 '14 at 15:54
Thanks for your answer! I'd rather someone get the bounty than no one! – AStupidNoob Feb 24 '14 at 4:05

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.

-
That's a really cool way of thinking about it! Now if only I knew what a "transfer matrix" was... – AStupidNoob Feb 26 '14 at 5:17