My task is to work out the generating function of $a_n$ series, in which $a_n$ is the number of ways to cover $2 \times n$ board with arbitrarily rotated blocks of type $A$ (bigger) and $B$ (smaller):
For the base of recurrence we should consider $n=1$ and $n=2$, as there is only one possibility in each case by filling the board with $2$ or $4$ blocks of type $B$. This means that $a_1 = a_2 = 1$.
The problem appears when I try to move to $n\geq 3$, as I cannot figure out how the recurrence relation should be defined, even though I can manually count the number of possible setups (it is quite time consuming though). My ideas related to this relation are:
- including $mod$ operation, as we are not always able to fit $A$ into $n$-th (new) column;
- in case we need to use multiple $a_n$ values, we can assume that $a_0 = 1$, as we can fill the $2\times 0$ board with no blocks, which is actually $1$ possibility,
but I am not sure whether these will be needed. I do not know how should I keep on working on this problem, so any tips would be appreciated. Finding the generating function based on recurrence relation is not an issue for me, thus I am not asking for any help with it.
Let $x_n$ and $y_n$ be the number of ways to fill $n$ columns and fill the upper square of the next column with a block of type $A$ or $B$, respectively. Then $x_0=x_1=0$ and $y_0=y_1=1$, and $x_n=x_{n-2}+y_{n-2}$ and $y_n=2x_{n-1}+y_{n-1}$. You can solve this two-dimensional recurrence and find $a_n=2x_{n-1}+y_{n-1}$.