ライツアウトの数理（4年ゼミ）

ライツアウト． $rank(M_n)$ の決定のつづき．
前回の細「中」と「中」の和として $rank(TM_n)$ を観察すると， $rank(M_n)$ より1つ落ちていることが分かる．
で，どうやって細「中」や「中」になることを示すか，という問題になるが，いっそのこと，一度境界のないcell automatonとしてどんな模様になるか先に計算したほうが何か分かるかも，ということに．
で， $\mod 2$ であることも忘れて，漸化式
$x_n^{t+1}=x_{n-1}^t+x_n^t+x_{n+1}^t$
で定まる数列を時刻 $t$ での情報で表示しようとした．
これはつまり， $\left(\frac{1}{x}+1+x\right)^t$ の展開係数を調べよう，ということに他ならない．
こうなると，関連した色々な道具が使えるようになるかと...
drive.google.com

[補足]
その後， $\omega$ を1の三乗根として
$x^2+x+1=(x-\omega)(x-\overline{\omega})$
とすれば，もう少し進められることに気付いた．

$\begin{align} (x^2+x+1)^t&=\left( (x-\omega)(x-\overline{\omega})\right)^t\\ &=\left(\sum_{k=0}^t{}_tC_k(-\omega)^{t-k}x^k\right)\left(\sum_{l=0}^t{}_tC_l(-\overline{\omega})^{t-l}x^l\right)\\ &=\sum_{m=0}^{2t}\left(\sum_{k+l=m}{}_tC_k\cdot{}_tC_l(-\omega)^{l-k}\right)x^m \end{align}$

そこで $x^m$ の係数 $A^t_m=\sum_{k+l=m}{}_tC_k{}_tC_l(-\omega)^{l-k}$ について，
$\begin{align} A^t_m &=\left(\sum_{k+l=m,k < l}+\sum_{k+l=m,k > l}+\sum_{k=l=m/2}\right){}_tC_k\cdot{}_tC_l(-\omega)^{l-k}\\ &=\sum_{k+l=m,k < l}{}_tC_k\cdot{}_tC_l\cdot2\Re\left( (-\omega)^{l-k}\right) +\left( {}_tC_{\frac{m}{2}}\right)^2 \end{align}$
と表示できる．ただし，末項は $m$ が偶数のときのみ存在する．また，
${ \begin{eqnarray} 2\Re\left( (-\omega)^{l-k}\right) = \left\{ \begin{array}{ll} (-1)^{l-k}\cdot 2 & \text{ when }l \equiv k \pmod{3}, \\ (-1)^{l-k+1} & \text{ when }l\not\equiv k\pmod{3} \end{array}\right. \end{eqnarray} }$
である．
具体的にいくらか計算すると，
$\begin{align} A^t_0&=1,\\ A^t_1&={}_t C_0 \cdot {}_t C_1 \cdot 2\Re( (-\omega))=t \\ A^t_2&={}_t C_0 \cdot {}_t C_2 \cdot 2\Re( (-\omega)^2)+({}_tC_1)^2=t^2-\frac{t(t-1)}{2}=\frac{t(t+1)}{2}\\ A^t_3&={}_t C_0 \cdot {}_t C_3 \cdot 2\Re( (-\omega)^3)+{}_t C_1 \cdot {}_t C_2 \cdot 2\Re( (-\omega)^1)=\frac{t(t-1)(t+4)}{6}\\ \end{align}$
といった具合になる．

ゼミの風景

おそらくお気楽はしのすけゼミの諸風景

ライツアウトの数理（4年ゼミ）