ナイトの移動の仕方の総数を行列で求める

問題

チェスの左上隅のマスから右下隅のマスへ, ナイトがちょうど$100$回で移動する移動の仕方の総数は?

解答例

チェスのマス目($8\times 8$)に$1$から$64$の番号付けをする.
$64$次正方行列$A=(a_{ij})$を次のように定める:
マス目$i$からマス目$j$へナイトが（$1$回で）移動できるとき$a_{ij}=1$, そうでないとき$a_{ij}=0$.

$n$を自然数とする. 行列$A^n$の$(i,j)$成分は, マス目$i$からマス目$j$へナイトがちょうど$n$回で移動できる移動の仕方の総数である.

$n$に関する帰納法

$A^{n-1}=(b_{ij})$とかくとき, $A^n$の$(i,j)$成分は$\sum_{k=1}^{64}b_{ik}a_{kj}$である.
一方, マス目$i$からマス目$j$へナイトがちょうど$n$回で移動できる移動の仕方の総数は
$$\sum_{k=1}^{64}(マス目i からマス目kへちょうどn-1回で移動できる移動の仕方の総数)\times (マス目k からマス目jへちょうど1回で移動できる移動の仕方の総数).$$

左上隅のマスを$1$, 右下隅のマスを$64$として（適当に）番号付けして$A$を作り,
$A^{100}$をコンピュータで計算して$(1,64)$成分を見ると, 全部で
$2593244602149234588139078903115618952040745476069710377506002611030781169300$通り.

投稿日：10月30日

この記事を高評価した人

高評価したユーザはいません

この記事に送られたバッジ

バッジはありません。

投稿者

すうさんぽ

669

代数学が好きです。ゆるく数学を歩いていきます。

他の人のコメント

コメントはありません。

読み込み中

すうさんぽ

ナイトの移動の仕方の総数を行列で求める