count the ways to fill a $4\times n$ board with dominoes

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!

I am not sure I can intuitively explain this recursive formula by itself (and don't think there is an easy explanation without going into numerous cases), but I wanted to give you a general approach that allows to derive such recursive expressions for any tiling problem $m\times n$.

First, I wanted to consider a slightly different problem: how many "connected" tilings on $m\times n$. By "connected" I mean the ones so that every two consecutive columns are connected by at least one tile. Let's call us this function $g(n)$.

We want to consider $g(n)$ mainly for two reasons:

1. It should be much easier to derive, partly due to the fact that initial tiles will determine the rest of the tiling, and partly due to the second point.

2. It is going to be periodic, i.e. there is some non-periodic part $g(1),\dots,g(N)$, and then there is a periodic "tail": for $k\ge 1$: $g(N+k)=g(N+k+T)$ for some fixed $T$.

The second property allows us to derive $f$ easily from $g$. Indeed, for every tiling let $k\ge 1$ be the maximum number so that the first $k$ columns are connected. Then, for every $k$ every possible tiling can be constructed as a connected tiling on the first $k$ columns, and then any tiling on the rest. In other words, for every $m,n$: $$f(n)=g(1)f(n-1)+g(2)f(n-2)+\dots+g(n)f(0) \tag{1}$$ where $f(0)=1$.

Now, if $g$ has a non-zero periodic tail, then the expression (1) will grow with $n$, but we can consider (1) for two values $n$ and $n-T$, and by subtracting one from the other we will obtain an expression with fixed finite number of terms. We can even write down this expression explicitly, where $g()$ has $N$ non-periodic terms and period $T$: $$f(n)=g(1)f(n-1)+\dots+g(T-1)f(n-T+1)+[g(T)+1]f(n-T)+[g(T+1)-g(1)]f(n-T-1)+\dots+[g(T+N)-g(N)]f(n-T-N) \tag{2}$$.

Let's look at how it works for different smaller values of $m$.

Tiles on $1\times n$: $m=1$. The number of connected tilings on $1\times n$ ($g(n)$) equals: $0,1,0,0,0,\dots$. Here $N=2$, $T=1$, but the tail is all zeros, so we do not need (2) to eliminate the tail. (1) gives us: $f(n)=f(n-2)$ with two initial terms $f(0)=1,f(1)=0$.

Tiles on $2\times n$: $m=2$. $g(n\ge 1)$ equals: $1,1,0,0,0,\dots$. Indeed, there are no connected tilings on $2\times n$ for $n\ge 3$. Once again, $N=2$ and $T=1$ with zero tail. (1) gives us $f(n)=f(n-1)+f(n-2)$ with initial terms $f(0)=1,f(1)=1$. This is just Fibonacci numbers. BTW, if we used (2), we would obtain another recursive sequence for Fibonacci numbers: $f(n)=2f(n-1)-f(n-3)$ with initial terms $f(0)=1,f(1)=1,f(2)=2$.

Tiles on $3\times n$: $m=3$. Here where it gets interesting, because it is the first time we will have a non-zero $g$-tail. $g(n)=0$ for odd $n$. $g(2)=3$: ⨅ ⨆ and ≡. $g(4)=g(6)=\dots=2$ (assume first that horizontal tile connecting the first two columns is top or bottom and construct the rest of connected tiling in unique way). So, $g(n)$ is $0,3,0,2,0,2,\dots$. Now, $N=2$ and $T=2$ and we have to use (2): $f(n)=4f(n-2)-f(n-4)$.

Finally, tiles on $4\times n$: $m=4$. First, we need to show that $g(n)$ for $n\ge 1$ equals $1,4,2,3,2,3,\dots$. The first two values (non-periodic part) is given (among 5 tilings of $4\times 2$ only one is disconnected). For $n>2$ consider three possible combinations of horizontal/vertical tiles covering the first column:

|    --   --
|    |    --
--   |    |
--   --   |

and show that each leads to a unique connected covering, and only two of them work for odd $n$. In this case (2) gives us: $f(n)=f(n-1)+5f(n-2)+f(n-3)-f(n-4)$.

The answer is here: A127864 or A077917.

The actual formula is: $f(n) = f(n-1) + 4 f(n-2) + 2 f(n-3)$. The sequence is: $1, 5, 11, 33, \dots$.

Let's split the tilings on N into 5 subtilings:

These are all possible board endings. Each tiling belongs to one and only one of these endings.

Number of tilings with ending of 1 and 5 are trivial to write recursively. As 2 and 3 are symmetrical, number of tilings in both of these groups is equal, denoted by g(N). Let number of tilings with ending 4 be denoted with h(N). So we have:

f(N) = f(N-2) + f(N-1) + 2*g(N) + h(N)

For type 2 (and 3) the following recursive relation holds:

g(N) = f(N-2) + g(N-1)

First part if the hole is filled with vertical tile, second if it is filled with 2 horizontal tiles (giving the symmetrical tiling on N-1).

For type 4 the following recursive relation holds:

h(N) = f(N-2) + h(N-2)

First part if the hole is filled with vertical tile, second if it is filled with 2 horizontal tiles (forcing horizontal tiles to be placed above and below the "bulge", giving repetition of the same structure on N-2).

Now we have a system of 3 equations of 3 recursive functions, which can be simplified as shown here: Simplify system of 3 equations of 3 recursive functions

Giving: $$f(n) = f(n - 1)+ 5·f(n - 2)+ f(n - 3) - f(n - 4) $$

P.S. Big thanks to @Sudix for simplifying the system of 3 equations on the referenced question. :)