2
$\begingroup$

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?

$\endgroup$
4
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ Thanks, I vaguely remember a formula like this and I believe Lior Pachter even gave a direct purely combinatorial proof. However my question also generalizes to cases where different small shapes can be used in the tiling (e.g. $2 \times 1$ dominoes and $2 \times 2$ squares and L-shapes of side length $2$ combined), and I'm still interested to know if the basic type of recursion I gave can be improved in any way. $\endgroup$ – user2566092 Jul 27 '14 at 16:24
  • $\begingroup$ @user2566092: I see. That wasn't clear from your question (the generalization). Perhaps you should create another question... $\endgroup$ – Aryabhata Jul 27 '14 at 16:26
  • $\begingroup$ Sure, I'll post another question with general small shapes and ask specifically about the recursion again. $\endgroup$ – user2566092 Jul 27 '14 at 16:30

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.