This is a problem from Brualdi and no solution is given for this.
The Question goes as .... Let g(n) be the number of different perfect covers of a 3-by-n chessboard by dominoes. Evaluate g(6).
I worked out a solution which goes like this.
I know the number of solutions for g(2) and g(4) (answer to g(4) was given in brualdi). I use those to compute g(6). g(6) can be broken up into 3 blocks of 3-by-2 dominoes so each block can be one the solutions of g(2) which is 3. So for this arrangement I get $3^{3}=27$ possible arrangements.
Next I break the 3-by-6 board into 3-by-2 and 3-by-4 boards. Here I'm careful to omit those solutions in g(4) that come due to the g(2) solutions. g(4) has 2 unique solutions. I use these to calculate and find $2*g(2)*(unique(g(4))=2*3*2=12$ more solutions.
Now this can be broken into two g(3) imperfect covers that can be combined appropriately. I'm having trouble convincing myself whether these coverings would be there or not! The same problem I had with n=4 in breaking it down to g(3) and g(1). I need help in figuring this out!
And, lastly if I found unique 3-by-6 coverings ( by unique I mean not utilising the other lower numbered (ie. 3-by-n, n<6 coverings) and found 2 more arrangements possible!
So, my current answer to this question >=41. I would be glad if someone could verify my process and clear my doubts.
You can solve this problem for all $n$, which may be instructive. If you are not familiar with recurrences, don't worry, just consider this is an extra verification of your answer.
Let $a_n$ count the number of perfect coverings of the $3\times n$ board. We call such boards type 1 boards.
Let $b_n$ count the number of perfect coverings of the $3\times n$ board where the top left corner (or the bottom left corner) is missing. We call such boards type 2 boards.
Let $c_n$ count the number of perfect coverings of the $3\times n$ board where the two upper squares (or the two lower squares) of the left column are missing. We call such boards type 3 boards.
There are three ways to cover the left column in a type 1 board (when $n>1$); if we use three horizontal domino's the remaining figure is type 1 again, in both other cases we need one horizontal and one vertical domino, and the remaining figure is a type 2 board, so we get $a_n=a_{n-2}+2b_{n-1}$. (1)
There are two ways to cover the left column of a type 2 board. Either we cover it with a vertical domino, leaving a type 1 board, or with two horizontal domino's, leaving a type 3 board, so we get $b_n=a_{n-1}+c_{n-1}$. (2)
There is only one way to cover the left column of a type 3 board. It leaves a type 2 board, so we get $c_n=b_{n-1}$. (3)
Equation (1) gives $b_{n-1}=\frac12(a_n-a_{n-2})$ (4), substituting (3) in (2) we get $b_n=a_{n-1}+b_{n-2}$ (5) and substituting (4) in (5) we get $a_n-4a_{n-2}+a_{n-4}=0$.
We see that the recurrence makes 'steps of 2'. This is intuitive, since $a_n$ is clearly 0 for all odd $n$. So it makes sense to introduce $d_n=a_{2n}$ and for $d_n$ we get the recurrence $d_n-4d_{n-1}+d_{n-2}=0$. This recurrence has characteristic equation $X^2-4X+1=0$, with solutions $p=2+\sqrt3$ and $q=2-\sqrt3$, so the general solution for the recurrence is $d_n=Ap^n+Bq^n$. (6)
Since $d_0=a_0=1$ (there is 1 way to tile the $0\times 3$ board: it uses no dominoes at all) and $d_1=a_2=3$ (by inspection), we can substitute $n=0$ and $n=1$ in (6) to get $A=1-B$ and $3=Ap+(1-A)q$, which solves to $A=\frac16(3+\sqrt3)$ and $B=\frac16(3-\sqrt3)$.
So the general solution we are looking for is $a_{2n}=d_n=\frac12(p^n+q^n)+\frac16\sqrt3(p^n-q^n)$.
Now compute $p^3+q^3=26+15\sqrt3$ and $p^3-q^3=26-15\sqrt3$ to see that the specific answer to this problem is $a_6=d_3=41$.
Phew.