How many ways are there to place $15$ pieces of size $1 \times 2$ into a $3 \times 10$ rectangle?

Question

How many ways are there to place $15$ pieces of size $1 \times 2$ into a $3 \times 10$ rectangle? (rotating and flipping are considered different ways)

I think this question might be solved by recursion. I tried to split each column to $(2,1)$, and split each row into groups of even numbers. But the groups of column and row sometimes can't be satisfied at the same time.

Any help or hint is appreciated. Thank you very much.

Answer 1

Recursion: we're tiling left to right. Let's say we have already tiled some part of the rectangle by somehow including leftmost untiled square, then we're left 7 possibilities of how the leftmost untiled squares (gray) look like:

  1       2       3      4       5       6      7

Let's denote $f_k(n)$ the number of ways we can tile $k$th case with $n$ full ($=$untiled) $3\times 1$ blocks after the leftmost (partially tiled as in 1-6 or untiled like in 7), so we're interested in $f_7(9)$.

We denote $\mathbf{f}(n)=(f_1(n),f_2(n),f_3(n),f_4(n),f_5(n),f_6(n),f_7(n),f_7(n-1))^T$ then $\mathbf{f}(n+1)=A\mathbf{f}(n)$ where $$A=\begin{pmatrix} 0&0&0&0&0&1&0&0\\ 0&0&0&0&1&0&0&0\\ 0&0&0&1&0&0&1&0\\ 0&0&1&0&0&0&0&0\\ 0&1&0&0&0&0&0&0\\ 1&0&0&0&0&0&1&0\\ 0&0&1&0&0&1&0&1\\ 0&0&0&0&0&0&1&0\\ \end{pmatrix}$$ and $\mathbf{f}(1)=(1,0,0,1,0,0,3,0)^T$. The rest (factorization of $A$ into $SDS^{-1}$ and computing $(0,0,0,0,0,0,1,0)SD^8S^{-1}\mathbf{f}(1)$ we left to WolframAlpha) and the answer is $571$.

Btw, looking up sequence A001835 it comes that the problem has a shorter solution:

$a(n) = 4\cdot a(n-1) - a(n-2)$, with $a(0) = 1,\, a(1) = 1.$

Can you find it? )