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?
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:
You can read here for more details: http://www.math.cmu.edu/~bwsulliv/domino-tilings.pdf