No.621

ひとつのマスのドミノには空き, 埋まっていて右にはみ出していない, 埋まっていて右にはみ出しているの3パターンある. 縦に連続して空きマスがあってはいけないという条件を合わせると, ひとつの列のマスの状態のパターンは $3^3-2 \times 2-1 = 22$ 通りである.

ひとつ前の列の状態から現在の列のどの状態に遷移できるかを考える.

これは, ひとつ前の列状態から現在の列の “埋まっていて右にはみ出していない” マスが埋まるので, ここから1行ごとに置かない, 縦に置く, 横に置くの場合を試せばいい. ただし, その行のひとつ前の列またはその列のひとつ前の行が空きであれば, そのマスは空きにはできない.

$i$ 番目の列のマスの状態パターンごとに組み合わせ数を並べたベクトルを $x_i$, ひとつ前の列の状態パターンから現在の列の状態パターンに遷移できる部分を $1$ にして, 残りを $0$ にした行列を $A$ とおくと, $x_i = Ax_{i-1}$ となり, これを解いて $x_i = A^ix_0$ となる. ただし, $x_0$ はすべてのマスが “埋まっていて右にはみ出していない” 状態が $1$ で残りは $0$ のベクトルである.

これを行列の繰り返し2乗法を使って計算し, 得られた $x_N$ のうち, “埋まっていて右にはみ出している” マスを含まない状態のパターン数をすべて足したものが答えとなる.