Rectangles and Dominoes.

Let $A_n$ be the number of ways of tiling a $4 \times n$ rectangle, and let $B_n$ and $C_n$ be the numbers of ways of tiling a $4 \times n$ rectangle which has had two squares cut off at one end, as shown:

By considering the different ways in which the end of a rectangle can be tiled, we deduce that $A_n \; = \; A_{n-1} + A_{n-2} + 2B_{n-1} + C_{n-1} \hspace{2cm} n \ge 3$

Similarly, we can show that $B_n \; = \; A_{n-1} + B_{n-1} \hspace{1cm} C_n \; =\; A_{n-1} + C_{n-2} \hspace{2cm} n \ge 3$

Since it is evident that $A_1=1\,,\,A_2 - 5$ , $B_1 = 1\,,\, B_2 = 2$ and $C_1 = 1\,,\,C_2 = 1$ , computation tells us that $A_6 = \boxed{281}$ .

My solution is a bit of a cheat compared to Mark's which gets an upvote from me.

I used the amazing formula for the number of ways of tiling an m by n board with dominoes

$\prod_{j=1}^{\lceil\frac{m}{2}\rceil} \prod_{k=1}^{\lceil\frac{n}{2}\rceil} \left ( 4\cos^2 \frac{\pi j}{m + 1} + 4\cos^2 \frac{\pi k}{n + 1} \right )$

I converted this to a computer program which takes the size of the board as input and gives the number of ways as output. After checking the program against easier cases, I have enough confidence in the formula to assert that the computation for a 4 by 6 board is correct.

Ways[4,6] = $\boxed{281}$

I found the formula in this wikipedia article.

By using the same analysis on my very similar problem , we obtain the answer 281 . It reduces the problem to counting the number of perfect matchings on a planar graph, which can be done in polynomial time using computer.

Of course, we can compute this number without computer either, if we diligently construct a recurrence system like in Mark Hennings' solution. But mine can be generalized to arbitrary $r \times c$ (and in fact to an arbitrary planar graph, so we can tile, say, a triangular board with diamonds, etc), while Mark's can only be generalized to $4 \times c$ ; a different number of rows requires recomputing the system from scratch.