# Tiling a rectangle with 2*1 tiles

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?

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