After solving this problem from SPOJ (count the ways to fill a 4xn board with 2×1 dominoes) I found a different solution while searching on internet.
This solution uses the recurrence relation $f(n) = f(n-1)+5f(n-2)+f(n-3)-f(n-4)$ where $f(n)$ denotes the number of ways to fill the $4\times n$ board with $2 \times 1$ dominoes.
I don't fully understand how someone gets that kind of relation (I don't know almost anything of combinatorics or recurrence relations) but I think I understand something. The $f(n-1)$ term comes from observing that there is an unique way to fill the last column and the $5f(n-2)$ term comes from observing there are 5 different ways to fill the last two columns.
But i don't get where the terms $f(n-3)-f(n-4)$ come from. So I have two questions, the first one is where these terms come from and second I'd like to ask you for a reference to learn combinatorics and recurrence relations.
May you help me? Thanks in advance.
-edit-
For my solution I used a binary number to represent what configurations of the i-th column was valid. For example 1001 represent that rows 1 and 4 are blocked in the i-th row because in the (i-1)th there is an horizontal domino in that positions. I calculated all the valid transitions such binary numbers could go to (I did this by hand for all the binary numbers from 0000 to 1111). Then I got a function which I programmed using dynamic programming and a technique called bitmask to represent the binary numbers as integers. The function is:
$f(i,mask) = \begin{cases} 0 &\mbox{if } i = n, mask \neq 0 \\
1 & \mbox{if } i = n, mask = 0. \\
\sum f(i+1,mask') &\mbox{else} \end{cases}$
Where mask' is taken from the set of all valid masks from where mask could transition to, also i=n means the first column outside the board as I considered 0-indexing. The code for that is here (this is not actually mine, it's from a mate but it's the exactly same idea).
Best Answer
There are eight ways in which a $4\times n$ tiling can begin, shown and named in the picture below. We'll count the number with each kind of beginning configuration and add the results up to get $f(n)$.
Types A through E are easy. Any $4\times (n-1)$ tiling can extend A to give a $4\times n$ tiling, and there are no other ways to get a "type A" $4\times n$ tiling. So there are $f(n-1)$ "type A" $4\times n$ tilings. Similarly, there are $f(n-2)$ type B $4\times n$ tilings, and $f(n-2)$ as well of each of the types C, D, and E. That's $f(n-1)+4f(n-2)$ so far.
Tilings with starting configurations F, G, and H are a little harder to count. First define some helpful notation.
Let $f_T(k)$ represent the number of $4\times k$ tilings of type T, where T is a set of starting configurations. That lets us say from what we have above that $$f(n)=f(n-1)+4f(n-2)+f_{\{F,G,H\}}(n)\textrm.$$ We just have to figure out $f_{\{F,G,H\}}(n)$ in terms of $f$.
Clearly $f_{\{F,G,H\}}(n)=f_{\{F\}}(n)+f_{\{G\}}(n)+f_{\{H\}}(n)$; we'll compute each term separately. Also take note of the fact that $f(k)=f_{\{A,B,C,D,E,F,G,H\}}(k)$.
Now on to the counting. We'll look at type F first.
A "type F" $4\times (n)$ tiling is always configuration F extended by a "type B" or "type F" $4\times (n-2)$ tiling that has its center left domino removed. So $f_F(n)$ is exactly the number of $4\times (n-2)$ "type B" or "type F" tilings, that is, $f_F(n)=f_{\{B,F\}}(n-2)$. (The type B and F tilings are exactly the ones that have a center left domino to remove.)
A "type G" tiling is G extended by a tiling of type A, C, or G, with the lower left domino removed, so $f_G(n)=f_{\{A,C,G\}}(n-2)$. (A, C, and G are the tiling types with a lower left domino.)
A "type H" tiling is H extended by a tiling of type A, D, or H, with the upper left domino removed. So $f_H(n)=f_{\{A,D,H\}}(n-2)$. (A, D, and H are the tiling with an upper left domino.)
Substituting these last three expressions into the previous displayed equation yields
$\begin{align*} f(n)&=f(n-1)+4f(n-2)+f_{\{B,F\}}(n-2)+f_{\{A,D,H\}}(n-2)+f_{\{A,C,G\}}(n-2)\\ &=f(n-1)+4f(n-2)+f_{\{A,B,C,D,F,G,H\}}(n-2)+f_{\{A\}}(n-2)\\ &=f(n-1)+4f(n-2)+f(n-2)-f_{\{E\}}(n-2)+f_{\{A\}}(n-2)\\ &=f(n-1)+5f(n-2)+f_{\{A\}}(n-2)-f_{\{E\}}(n-2) \end{align*}$
Fortunately, A and E are the simplest patterns, and we know from our initial calculations (which we did before adopting the subscript notation on $f$) that $f_{\{A\}}(n-2)= f(n-3)$ and $f_{\{E\}}(n-2)= f(n-4)$. These final calculations give the recurrence relation you asked about: $$f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)\textrm.$$
I'll let someone else suggest good references for learning these techniques and just say experience helps. The hundredth one is a lot quicker to figure out than the first one!