　一般に $4\times4n$ のマス目をT字のタイルで敷き詰める方法が $a_n$ 通りだけあるとする．最も左からタイルを置くことを考えると，下図のように

$\quad (A)$ 左の $4$ 列で区切りができる場合\
$\quad (B)$ 左の $4$ 列で区切りができない場合

で場合分けできる．
![figure 1](\/images\/uwZ92FJ3UX0x6ZBnb2khT3fKufC6GdTvLWXC2v5Y)
![figure 1](\/images\/ry8kdjuJOZ4aolKi7taSvvSVsvktDQ188OupiwSe)

　$(A)$ となるような敷き詰め方は $2$ 通りあり，さらに残りの $4(n-1)$ 列の敷き詰め方は $a_{n-1}$ 通りだけあるため，合計で $2a_{n-1}$ 通りである．\
　$(B)$ となる場合，左の $4$ 列からはみ出した $4$ マスを一つのタイルとみなすことで，敷き詰め方は合計で $a_{n-1}$ 通りであることがわかる．\
　以上より次の漸化式が成り立つ．
$$a_n=3a_{n-1}$$
これと $a_1=2$ より，求める値は $a_{10}=2\cdot3^9=\mathbf{39366}$ 通りである．
公式解説
https://onlinemathcontest.com/contests/hamamatsu2024/editorial/9286
　実験すると考えるのは上下に向きのある $4\times 4n$ の長方形をならべて, $4\times 40$ のマス目を覆う方法の数であるとわかり, 
$$f=2x+2x^2+2x^3+\cdots=\frac{2x}{1-x}$$
とすると, ちょうど $k$ 個の長方形でマス目を覆う方法の数は $\[x^{10}\]f^k$ であり, ( $f$ の各項の係数 $2$ は上下 $2$ 通りに対応.) これを, $k=0,1,2,\cdots$ について合計すると求める答えは,
$$
\begin{aligned}
\sum_{k=0}^{\infty}\[x^{10}\]f^{k}&=\[x^{10}\]\sum_{k=0}^{\infty}f^{k}\\\\
&=\[x^{10}\]\frac{1}{1-f}\\\\
&=\[x^{10}\]\frac{1}{1-\dfrac{2x}{1-x}}\\\\
&=\[x^{10}\]\frac{1-x}{1-3x}\\\\
&=\[x^{10}\]\frac{1}{1-3x}-\[x^{9}\]\frac{1}{1-3x}\\\\
&=3^{10}-3^{9}\\\\
&=2\times3^9
\end{aligned}
$$
ユーザー解説
https://onlinemathcontest.com/contests/hamamatsu2024/editorial/9286/656
　図のような $\textrm T$ 字のタイルをちょうど $40$ 枚用いて，$4\times40$ のマス目を重なりや隙間，はみ出しなく敷き詰める方法は何通りありますか？　ただし，タイルを回転させてもよく，それぞれのタイルは区別しません．また，回転および裏返しで一致する敷き詰め方は別のものとして数えます.

![figure 1](\/images\/XZhL5lZ3U7YvqMzqOmldilrZnISpqP9Jo3S8cOeU)