I am trying to find the number of distinct possible tilings of $2 \times n$ board using only $2 \times 1$ tiles, such that no tiles overlap, go beyond the board boundary and the board is completely tiled with no gaps.
I have approached this problem the classical way by finding a recursive relationship between three consecutive terms leading us to solve the problem using the Fibonacci sequence.
However this exploration shows that it is possible to solve the problem without having to compute any sub-problems by considering the different transitions between columns. On page 4 of this exploration, I am struggling to understand how the matrix $A$ keeps track of where we are allowed to move and why it has been defined as
$$A = \begin{bmatrix}1 & 1\\1 & 0\end{bmatrix}$$
and I am unable to understand what the $B_k$ matrix does and why it has been defined as
$$B_k = \begin{bmatrix}b^k_{11} & b^k_{12}\\b^k_{21} & b^k_{22}\end{bmatrix}$$
From these matrices I struggle to understand how we can compute the number of distinct tilings on a $2 \times n$ board.
Could somebody explain this to me?
First of all, note that the $^k$ on the entries of $B_k$ are not exponents. They are indices. But because we also need indices to determine what entry of the matrix it represents, the $k$ index has been pushed up.
With that said, $B_0 = I$ and $B_1 = A$. And in general, the entry $b_{ij}^k$ tells you how many different ways you can tile a gap that is $k$ wide if the left-hand side of the gap is of type $i$ and the right-hand side of the gap is of type $j$.
For instance, the fact that $b_{22}^1 = 0$ tells you that there are no tilings of a gap of width 1 such that both ends of the gap are of type $2$. Similarily, $b_{11}^2 = 2$ tells you that a gap of width 2, with both ends being of type 1, may be tiled in two ways.
We see that $B_{k+1} = B_kA$, which gives us $B_k = A^k$. So the entries of $A^n$ tells us how many ways there are to tile a $2\times n$ rectangle. Specifically, since the ends of the rectangle are of type 1 (no domino is allowed to go over the edge), the top left entry of $A^n$ is our answer.