Finding a recursive formula for combinatorial problem

164 Views Asked by At

I need help with a HW question.

EDIT you can rotate and reflect

Question

Let $f(n)$ denote the number of different ways to fill the shape $2 \times n$ with the $2$ shapes below: enter image description here

find recursion formula for $f(n)$

My attempt

$f(1)=1$

$f(2)=2$ because:

enter image description here

$f(3)=5$ because:

enter image description here

for $n\ge 4$ ,I want to express $f(n)$ with $f(j)$ for $j<n$. So I tried to fill part of the shape and understand the formula, but every time I think about it from the start to check my answer - I get a different recursion formula.

I added below a part of my sketch for better understaning my difficulty solve the problem: enter image description here

Thank you!

EDIT:Attempt 2

enter image description here

EDIT:Attempt 3

enter image description here

1

There are 1 best solutions below

11
On
  1. For the $2 \times (n-1)$ case, both the figures are stating the same case. So if you have already constructed a $2 \times (n-1)$ board, then to get to the $2 \times n$ board you just need to add the rectangular tile in the end. Thus far, it gives us: $$f(n)=f(n-1)+\text{other ways to construct a }2 \times n \text{ board}.$$
  2. Now consider the other case, where you have a $2 \times (n-3)$ board already constructed. And you have to fill the $2 \times 3$ vacant spaces to tile the $2 \times n$ board. You have considered two possibilities in your diagram and they are independent of each other. But there can be more. For example, you can have the following:

$$\begin{array}{ccc} \color{red}{l}&\color{red}{l}&\color{red}{l}&\\ r&r&\color{red}{l} \end{array}, \qquad \begin{array}{ccc} \color{red}{l}&r&r\\ \color{red}{l}&\color{red}{l}&\color{red}{l} \end{array}, \qquad \begin{array}{ccc} \color{red}{l}&\color{red}{l}&\color{red}{l}\\ \color{red}{l}&r&r \end{array}, \qquad \begin{array}{ccc} r&r&\color{red}{l}\\ \color{red}{l}&\color{red}{l}&\color{red}{l} \end{array} $$ Thus we will have $4$ independent ways to complete the tiling. So, $$f(n)=f(n-1)+4f(n-3)+\text{(think: is this it? or do we need any more cases, e.g. $2 \times (n-2)$?)}$$