Combinatorics and T-tetromino

Question

In how many ways can I fill a grid $4 \times N$ with only T-tetrominoes? my idea is that it's possible to fill it if and only if $N$ is a multiple of $4$, in that case the solution is: \begin{equation} \bigg \{ \begin{array}{rl} 2^{N/4} & N \text{ is multiple of } 4,\\ 0 & \text{otherwhise}.\\ \end{array} \end{equation} Is that correct? It seems too easy!

Answer 1

I think your answer is acceptable. I think you mean to have T-tetronimos made of 4 bricks as in the picture. This way I can see just 2 solutions for N=4 and 2^2 solutions for N = 8. There are no solutions for N%4 != 0.

See the image below:

Answer 2

At first we can show that if $N$ is not divisible by $4$ the answer is $0$. Let's consider $4$ types of cells identified by diagonals: $$\begin{array}{|c|c|c|c|c} \hline 1 & 2 & 3 & 4 & 1 & \\\hline 4 & 1 & 2 & 3 & 4 & \\\hline 3 & 4 & 1 & 2 & 3 & \\\hline 2 & 3 & 4 & 1 & 2 & \\\hline \end{array} \begin{array}{c} \cdots\\\cdots\\\cdots \end{array}$$ It is easy to see that any $4 \times N$ field has equal number of cell of each type. Each T-tetramino takes $2$ cells of one type (let's call it main type), $1$ cell of each of two other types, the $0$ cells of the remaning type. This means that filling has the same number of tetraminoes for each of $4$ main types. Therefore total number of cells is divisible by $16$ and then $N$ is divisible by $4$.

Let's call a filling solid if each inner vertical line (crossing $4$ lines) contains inner point of some tetramino. Each filling can be splitted into a set of solid fillings. If $f(N)$ is the number of all fillings of field $4 \times N$ and $g(N)$ is the number of solid fillings of the same field, then $$f(n) = \sum_{K = 1}^{N/4}g(4K)f(N - 4K).$$

Now let's compute $g(N)$. Upper left corner cell can be covered in two ways: $$\begin{array}{|c|c|c|c} \hline 1 & 1 & 1 & ~ & \\\hline & 1 & & & \\\hline & & & & \\\hline & & & & \\\hline \end{array} \begin{array}{c} \cdots\\\cdots\\\cdots \end{array}\qquad \begin{array}{|c|c|c|c} \hline 1 & & ~ & \\\hline 1 & 1 & & \\\hline 1 & & & \\\hline & & & \\\hline \end{array}\begin{array}{c} \cdots\\\cdots\\\cdots \end{array}$$ That implies $$\begin{array}{|c|c|c|c} \hline 1 & 1 & 1 & & \\\hline 2 & 1 & & & \\\hline 2 & 2 & 3 & & \\\hline 2 & 3 & 3 & 3 & \\\hline \end{array} \begin{array}{c} \cdots\\\cdots\\\cdots \end{array}\qquad \begin{array}{|c|c|c|c} \hline 1 & 3 & 3 & 3 & \\\hline 1 & 1 & 3 & & \\\hline 1 & 2 & & & \\\hline 2 & 2 & 2 & & \\\hline \end{array}\begin{array}{c} \cdots\\\cdots\\\cdots \end{array}$$ These two cases are symmetrical reflection of each other, so we can consider any of them and multiply result by $2$. If $N = 4$ we can place one more tetramino to fininish filling:

$$\begin{array}{|c|c|c|c|} \hline 1 & 1 & 1 & 4 \\\hline 2 & 1 & 4 & 4 \\\hline 2 & 2 & 3 & 4 \\\hline 2 & 3 & 3 & 3 \\\hline \end{array}$$

If $N > 4$ the only way to continue is the following: $$\begin{array}{|c|c|c|c} \hline 1 & 1 & 1 & 4 & 7 & 7 & 7 & \\\hline 2 & 1 & 4 & 4 & 4 & 7 & & \\\hline 2 & 2 & 3 & 5 & 5 & 5 & 6 & \\\hline 2 & 3 & 3 & 3 & 5 & 6 & 6 & 6 \\\hline \end{array} \begin{array}{c} \cdots\\\cdots\\\cdots \end{array}$$

This is absolutely the same situation: for $N = 8$ we can finish filling and for $N > 8$ we have exactly $1$ way to continue. Therefore $g(N) = 2$.

$f(4) = 2$ and we have $$f(N) = \sum_{K = 1}^{N / 4}g(4K)f(N - 4K) = 2\sum_{K = 1}^{N / 4}f(N - 4K)\\ = 2f(N - 4) + 2\sum_{K = 1}^{N / 4 - 1}f(N - 4 - 4K) = 3f(N - 4).$$ Therefore we have $f(N) = [4 \mid N]2 \cdot 3^{N / 4 - 1}$ for $N \ge 1$ and $f(0) = 1$.