5
$\begingroup$

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$? enter image description here

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.

$\endgroup$
3
$\begingroup$

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.

$\endgroup$
  • $\begingroup$ 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? $\endgroup$ – idknuttin Sep 13 '16 at 16:35
  • 1
    $\begingroup$ Yes, see my edited answer. $\endgroup$ – Robert Z Sep 13 '16 at 16:36
2
$\begingroup$

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.

$\endgroup$

Your Answer

By clicking “Post Your Answer”, you agree to our terms of service, privacy policy and cookie policy

Not the answer you're looking for? Browse other questions tagged or ask your own question.