# How to count number of ways to tile a board of the size $2 \times 10$?

In how many ways can we tile the board of the size $2 \times 10$ using the pieces of the format $2×1$, $1×2$, and $2×2$?

The picture above shows six different tilings of the board $2×10$ using the described pieces.

I have an idea of how to do it the long way by first counting the number of ways to tile with just using the $2×2$ and $1×2$, then I could do the same thing for the other two combinations then eventually counting the number of ways when using all three sizes, but I want to learn how to solve it the quicker way and using math.

I have a textbook in applied combinatorics, what do I need to learn in order to solve a problem like this? I think this has to do with recursion but I am not completely sure.

Let $A_n$ be the number of tilings of the board $2\times n$. Note that $A_1=1$ and $A_2=3$. Moreover for $n\geq 3$ the following linear recurrence holds $$A_n=A_{n-1}+2A_{n-2}.$$
In fact consider the rightmost tile(s) of a tiling of $2\times n$. Either it is a $2\times 1$, two $1\times 2$ or one $2\times 2$.
If it is a $2\times 1$, then removing we have a valid tiling of $2\times (n-1)$.
In the other TWO cases, then after removing them we have a valid tiling of $$2\times (n-2). Finally it is now easy to compute the first ten numbers: 1, 3, 5, 11, 21, 43, 85, 171, 341, 683. See here for more properties of this sequence. • I drew all the possible ways to tile a 2 \times 3 board and got 5, same as if I used A_n = A_{n-1} + 2A_{n-2}, so now all I have to do is prove A_n = A_{n-1} + 2A_{n-2} by using strong induction and plug in n=4, 5, ..., 10 to find the answer? – idknuttin Sep 13 '16 at 16:35 • Yes, see my edited answer. – Robert Z Sep 13 '16 at 16:36 Let the number of tilings of a 2\times n board with the given tiles be z_n. We have z_1=1 and z_2=3. Given a 2×n board whose leftmost n-1 columns are filled, I can add a single vertical domino to complete the tiling. If the leftmost n-2 columns are filled, I can add either a 2×2 block or two horizontal dominoes to complete the tiling without forming a tiling of the leftmost n-1 columns (two vertical dominoes do this, so are rejected). This establishes the recurrence relation$$z_n=z_{n-1}+2z_{n-2}$$and z_{10} can be found by continuing up the indices:$$z_1=1,z_2=3\{z_1,z_2,z_3,\dots,z_{10}\}=\\ \{1,3,5,11,21,43,85,171,341,683\} Hence there are 683 ways to tile a $2×10$ board with the given conditions. This is the Jacobsthal sequence, indexed as A001045 in the OEIS.