Combinatorics and Recurrence Relationship

Question

I am finding out the recurrence relationship for a checkboard 2xn. I got 1-squares(1x1) and L shape, 3-squares to choose from to cover the table. n>=1

So $a_1= 1$ since its just two 1-squares and $a_2= 5$ (all 1-squares + 4 ways to rotate one L-square and fill the rest with 1-squares ).

Next, I take $a_3$ and as always; one way to choose all 1-squares, eight ways to use one L-square and since this is just two versions of the previous checkboard (4 ways + 4 ways), two ways to use two L-squares $a_3 = 1 + 8 + 2 =11$ ways.

From this $a_4 = 2*11+5 = 27$ ways and the recurrence relationship is $a_n=2a_{n-1}+a_{n-2}$? - but that has not the base case for two L's.

When I tried to brute force a4 by drawing all the combinations I end up with 33 (not 27), one way to choose all 1-squares, 12 ways to use one L-square and rest 1-squares and 20 ways of using two L-square and rest 1-squares. That would give the RR of $a_n=a_{n-1}+4a_{n-2}+2a_{n-3}$ to include the 3 base case?

Answer 1

Here, the recurrence relation would be $$a_n = a_{n-1} + 4a_{n-2} + 2a_{n-3}$$

From your explanation itself, there are three unique cases that all covering can be broken down into

1. Using singles
2. Using a combination of singles and L blocks
3. Using only L blocks

Now, since the smallest block you can make with two L blocks is 2x3, that will have to factor into your base case.

In general, assume you have a fully covered 2x(n-1) board, and you add an aditional 2 tiles at the end to make it 2xn

Case 1: Use singles for the new squares - number of ways is $a_{n-1}$

Case 2: Use L-blocks and singles for the last 4 squares - number of ways is $4a_{n-2}$

Case 3: Use only L-blocks for the last 6 squares - number of ways is $2a_{n-3}$

Answer 2

You are correct that $a_4=33$. If you try to account those 33 diagrams with your formula, you may well discover what your missing cases have in common.

The actual recurrence relation is $a_n=a_{n-1}+4a_{n-2}+2a_{n-3}$. There is exactly one way to fill a $2\times n$ rectangle such that the first $n-1$ rows are also a complete rectangle (two monominoes, as you note), four ways such that the first $n-2$ rows is the maximum rectangle from the left (one L and one monomino), and two ways such that the first $n-3$ rows is the maximum rectangle from the left (two L's).