2
$\begingroup$

Suppose we have a rectangle $a$ units wide and $b$ units long. How many ways are there to tile it with $2$-by-$1$ 'domino' tiles? (For the purposes of this question, let's count rotational and mirror image symmetries separately)

Let $F(a,b)$ = total number of ways to tile the rectangle.

When $a=2$, the case is quite simple.

$F(2,2) = 2$

$F(2,3) = 3$

$F(2,4) = F(2,2) + F(2,3) = 2 + 3 = 5$. This is because we can take all the $F(2,3)$ possibilities and add one domino (in the 'wide' orientation) on the right hand end, to yield three possibilities. Two more new possibilities are added by taking the $F(2,2)$ possibilities, and adding two dominoes (in the 'long' orientation) at the right hand end. Consequently, the $F(2,b)$ sequence is the Fibonacci numbers.

As far as I can calculate, $F(4,3) = 11$; and $F(4,4) = 36$. Any thoughts? Is the function $F(a,b)$ known?

$\endgroup$
2
  • $\begingroup$ I myself have no good idea about it, but have you considered giving a read on the Wikipedia article about Domino tiling? $\endgroup$ Commented Jul 7, 2017 at 2:47
  • $\begingroup$ You may be able to reformulate as DP $\endgroup$
    – qwr
    Commented Jan 27, 2020 at 16:37

1 Answer 1

3
$\begingroup$

Domino tiling can be seen as finding a perfect matching in the bipartite graph of the shape. There is a function that can be seen here:

enter image description here

You can read here for more details: http://www.math.cmu.edu/~bwsulliv/domino-tilings.pdf

$\endgroup$

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .