1
$\begingroup$

There's a problem in our combinatorics class:

enter image description here

As you can see above we have a number of blocks (either of size 2x1 or 2x2). We need to fill a big block of size $2$x$n$ with these "small" blocks. The 2x1 blocks can be arranged either vertically or horizontally. So for example if we had a block of size 2x2 we could:

  1. fill it with 2 horizontal 2x1 blocks
    1. fill it with 2 vertical 2x1 blocks
    2. lastly we could fill it with one 2x2 block

In total 3 options. Below is another example of a possible block to be filled: enter image description here

We need to find the recurrence relation for this. I came up with this: $$a_n=a_{n-1}+3a_{n-2}$$ because if we use a 2x1 block vertically we have $n-1$ space to fill. If we place 2 vertical or 2 horizontal blocks or one square block (3 possibilities) then we need to fill $n-2$ space.

I'm not sure this is correct though. Also does $a_0$ equal $1$ or $2$?

$\endgroup$
4
  • $\begingroup$ Actually, the recurrence should be $a_n=a_{n-1}+2a_{n-2}$, with $a_0=1$. $\endgroup$
    – Hrhm
    Commented Sep 24, 2016 at 13:39
  • $\begingroup$ Thanks! But why don't we need to take into account 3 options but just 2 as in your case? $\endgroup$
    – Yos
    Commented Sep 24, 2016 at 13:40
  • $\begingroup$ I'll type out a detailed answer below, explaining comment. $\endgroup$
    – Hrhm
    Commented Sep 24, 2016 at 13:42
  • $\begingroup$ Your third case, where you fill in the remaining $2\times 2$ box with vertical bars is invalid, since those tilings have already been considered. You already counted these tilings when you considered the case in which the first $2\times (n-1)$ is filled. $\endgroup$
    – Hrhm
    Commented Sep 24, 2016 at 14:05

1 Answer 1

3
$\begingroup$

Actually, the recurrence is $a_n=a_{n-1}+2a_{n-2}$. To understand why, let's consider a simple case. Say we already know that $a_1=1$ and $a_2=3$. Let's figure out $a_3$. Following your line of logic, we can fill in the the first $2\times 2$ box in 3 ways (since $a_2=3$). This forces us to fill in the remaining space with 1 vertical bar. So far, then, we have three possible tilings:

Tiling 1 Tiling 2 Tiling 3

Next, consider the tilings in which we fill the first $2\times 1$ box. This can be done in 1 way (since $a_1=1$). Now, you might be tempted to say that, since the right $2\times 2$ box can be filled in 3 ways, we have three additional tilings:

Tiling 4 Tiling 5 Tiling 6

But, as you can see, one of these tilings has already been counted (the one on the top). This means that we only have a total of 5 tilings. So, in summary: $$a_3=a_2+2a_1=3+2\cdot1=5$$

You can generalize this to get the following recurrence: $$a_n=a_{n-1}+2a_{n-2}$$

If you let $n=2$, you can see that $a_0$ must be $1$.

$\endgroup$
0

You must log in to answer this question.

Not the answer you're looking for? Browse other questions tagged .