# Smarter recursion to compute #tilings of $m \times n$ board with small shapes that fit in $2 \times 2$ square?

This is a generalization of another question I posted because I wasn't clear that I cared about more than $2 \times 1$ dominoes (it's just a special case), and there is an explicit tractable formula for $2 \times 1$ dominoes. I was wondering about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with a given subset of the contiguous shapes that are subregions of a $2 \times 2$ square (the $1 \times 1$ square, $2 \times 1$ dominoes, the $2 \times 2$ square, and the L-shapes).

If $m \leq n$, then we can use recursion on $n$ by keeping track of the which squares are filled in the $n$th column, which gives $2^m$ cases to keep track of for each value of $n$, with the cases related between $n-1$ and $n$ based on how the empty spaces in the $(n-1)$th column are filled with the various shapes.

I was wondering, are there any significant improvements possible for this type of recursion? For example can we take advantage of some symmetries somehow? If improvements are possible, can it change the asymptotics for the computational time? For the current recursion, if the coefficients expressing cases for the $n$th column in terms of cases for the $(n-1)$th column are precomputed, then the running time is $O(nM)$ where $M = O(2^{2m})$ is the number of non-zero coefficients. If $n \gg m$ then successive matrix squaring can be used to get the running time to $O(2^{3m} \log n)$.

• (Just a guess) You can try a dynamic programming. – pushpen.paul Jul 27 '14 at 18:28