Smarter recursion to compute #tilings of $m \times n$ board with $2 \times 1$ dominoes? So I was thinking about how to computationally (e.g., with recursion) obtain the number of tilings of an $m \times n$ board with $2 \times 1$ dominoes. 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 horizontal and vertical dominoes. I was wondering, are there any significant improvements known for this type of recursion? For example can we take advantage of symmetry somehow and e.g. only keep track of the lengths of the contiguous filled squares and contiguous empty squares? Or other improvements? If improvements are possible, does it change the asymptotics of the number of cases that need to be tracked?
From my answer on math.SE:

If you just used $1\times2$ rectangles, then this is same as finding the number of matchings in the $m \times n$ rectangle graph, and a formula for that has been given by Kastelyn:

$$ \sqrt{\left|\prod_{j=1}^{m}\prod_{k=1}^{n} \left(2 \cos \frac{\pi j}{m+1} + 2i\cos \frac{\pi k}{n+1}\right)\right|}$$

This was done, by mapping the number to the square root of the determinant of a weighted adjacency matrix of the graph.

You can find a nice exposition for the $1\times 2$ case in the first chapter of Kenyon's lecture notes.