Advent calendar 2019
4 December
There are 5 ways to tile a 3×2 rectangle with 2×2 squares and 2×1 dominos.
Today's number is the number of ways to tile a 9×2 rectangle with 2×2 squares and 2×1 dominos.
Show answer
Hide answer
Let \(a_n\) be the number of ways to tile an \(n\times2\) rectangle.
There is one way to tile a 1×2 rectangle; and there are three ways to tile a 2×2 rectangle. Therefore \(a_1=1\) and \(a_2=3\).
In a \(n\times2\) rectangle, the rightmost column will either contain a vertical 2×1 domino, two horizontal 2×1 dominoes, or a 2×2 square.
Therefore \(a_n=a_{n-1}+2a_{n-2}\).
Using this, we find that there are 341 ways to tile a 9×2 rectangle.
