トリボナッチ数列と行列 - pencoderのブログ

トリボナッチ数列の計算*1

フィボナッチ数列に類似した数列にトリボナッチ数列があります．フィボナッチ数列は最初の2項を初期値とし，3項目以降を直前の2項の和として定めていますが，トリボナッチ数列は最初の3項を初期値とし，4項目以降を直前の3項の和として定めています．

トリボナッチ数列 $T = (T_0, T_1, T_2, \cdots)$ は以下のように定義されます．

$\displaystyle \begin{equation} \begin{cases} T_0 = 0 \\ T_1 = 0 \\ T_2 = 1 \\ T_k = T_{k-3} + T_{k-2} + T_{k-1} & (k = 3, 4, 5, \cdots) \end{cases} \end{equation}$

トリボナッチ数列の具体的な値を以下の表に示します．

$n$	0	1	2	3	4	5	6	7	8	9	10	11	12	13	14	15	16	17	18	19	20	21	22	23	24	25	26	27	28	29	30	$\cdots$
$T_n$	0	0	1	1	2	4	7	13	24	44	81	149	274	504	927	1705	3136	5768	10609	19513	35890	66012	121415	223317	410744	755476	1389537	2555757	4700770	8646064	15902591	$\cdots$

$k = 0, 1, 2, \cdots$ について， $T$ の連続した3つの要素を成分にもつベクトル $\boldsymbol{t}_k$ を以下のように定義します．

$\displaystyle \begin{equation} \boldsymbol{t}_k = \begin{pmatrix} T_{k+2} \\ T_{k+1} \\ T_k \end{pmatrix} \end{equation}$

以下の線形変換 $f \colon \mathbb{R}^2 \to \mathbb{R}^2$ は $\boldsymbol{t}_k$ を $\boldsymbol{t}_{k+1}$ に写します．

$\displaystyle \begin{equation} f\left(\begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix}\right) = \begin{pmatrix} x_1 + x_2 + x_3 \\ x_1 \\ x_2 \end{pmatrix} \end{equation}$

線形変換は行列により表すことができます．変換 $f$ を表す行列を $A$ とすると， $A$ の各列には基本ベクトル $\boldsymbol{e}_1, \boldsymbol{e}_2, \boldsymbol{e}_3$ をそれぞれ $f$ で変換した $f(\boldsymbol{e}_1), f(\boldsymbol{e}_2), f(\boldsymbol{e}_3)$ が並びます．これは線形変換において，基本ベクトルの変換先の情報のみを用いて任意のベクトルの変換先を計算できるためです．

$\displaystyle \begin{gather} f(\boldsymbol{e}_1) = f\left(\begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix}\right) = \begin{pmatrix} 1 + 0 + 0 \\ 1 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} \\ f(\boldsymbol{e}_2) = f\left(\begin{pmatrix} 0 \\ 1 \\ 0 \end{pmatrix}\right) = \begin{pmatrix} 0 + 1 + 0 \\ 0 \\ 1\end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} \\ f(\boldsymbol{e}_3) = f\left(\begin{pmatrix} 0 \\ 0 \\ 1 \end{pmatrix}\right) = \begin{pmatrix} 0 + 0 + 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \end{gather}$

より，

$\displaystyle \begin{equation} A = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{pmatrix} \end{equation}$

となります．

$\displaystyle \begin{equation} A \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \\ \end{pmatrix} \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} = \begin{pmatrix} x_1 + x_2 + x_3 \\ x_1 \\ x_2 \end{pmatrix} \end{equation}$

より， $A$ は $f$ と同じ変換を表すことが分かります．

上の計算を丁寧に書くと以下のようになります．計算には変換の線形性が利用されています．

$\displaystyle \begin{align} A \begin{pmatrix} x_1 \\ x_2 \\ x_3 \end{pmatrix} & = A(x_1 \boldsymbol{e}_1 + x_2 \boldsymbol{e}_2 + x_3 \boldsymbol{e}_3) \\ & = x_1 A \boldsymbol{e}_1 + x_2 A \boldsymbol{e}_2 + x_3 A \boldsymbol{e}_3 \hspace{10pt} (\because \text{変換の線形性}) \\ & = x_1 \begin{pmatrix} 1 \\ 1 \\ 0 \end{pmatrix} + x_2 \begin{pmatrix} 1 \\ 0 \\ 1 \end{pmatrix} + x_3 \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \\ & = \begin{pmatrix} x_1 + x_2 + x_3 \\ x_1 \\ x_2 \end{pmatrix} \end{align}$

$A$ による $n$ 回の変換は行列の累乗 $A^n$ で表されるので， $\boldsymbol{t}_n$ は以下の式で計算できます．

$\displaystyle \begin{equation} \boldsymbol{t}_n = A^n \boldsymbol{t}_0 = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} \end{equation}$

ただし， $A^0$ は恒等変換を表す単位行列とします．

$\boldsymbol{t}_n = \begin{pmatrix} T_{n+2} \\ T_{n+1} \\ T_n \end{pmatrix}$ より， $T_n$ は $\boldsymbol{t}_n$ の第3成分として求めることができます．これは $A^n$ の $(3, 1)$ 成分に一致します．

例えば $T_8$ は

$\displaystyle \begin{equation} \boldsymbol{t}_8 = \begin{pmatrix} 1 & 1 & 1 \\ 1 & 0 & 0 \\ 0 & 1 & 0 \end{pmatrix}^8 \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 81 & 68 & 44 \\ 44 & 37 & 24 \\ 24 & 20 & 13 \end{pmatrix} \begin{pmatrix} 1 \\ 0 \\ 0 \end{pmatrix} = \begin{pmatrix} 81 \\ 44 \\ 24 \end{pmatrix} \end{equation}$

より， $24$ であると分かります．

$n$ が大きいとき， $A^n$ の計算に繰り返し2乗法を用いることで計算の高速化を図ることができます．

一般化

フィボナッチ数列やトリボナッチ数列を一般化した数列として，最初の $N$ 項を初期値とし， $N+1$ 項目以降を直前の $N$ 項の和として定めた数列 $F = (F_0, F_1, F_2, \cdots)$ を考えます． $F_n$ は以下の式により求められるベクトルの第 $N$ 成分として求めることができます．

$\displaystyle \begin{equation} \begin{pmatrix} 1 & 1 & 1 & & 1 & 1 & 1 \\ 1 & 0 & 0 & \cdots & 0 & 0 & 0 \\ 0 & 1 & 0 & & 0 & 0 & 0 \\ & \vdots & & \ddots & & \vdots & \\ 0 & 0 & 0 & & 0 & 0 & 0 \\ 0 & 0 & 0 & \cdots & 1 & 0 & 0 \\ 0 & 0 & 0 & & 0 & 1 & 0 \\ \end{pmatrix}^n \begin{pmatrix} F_{N-1} \\ F_{N-2} \\ F_{N-3} \\ \vdots \\ F_2 \\ F_1 \\ F_0 \end{pmatrix} \end{equation}$

$N = 2, F_0 = 0, F_1 = 1$ のとき $F$ はフィボナッチ数列となり， $F_n$ は以下で計算されるベクトルの第2成分として求めることができます．

$\displaystyle \begin{equation} \begin{pmatrix} 1 & 1 \\ 1 & 0 \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \end{pmatrix} \end{equation}$

$N = 4, F_0 = F_1 = F_2 = 0, F_3 = 1$ のとき $F$ はテトラナッチ数列となり， $F_n$ は以下で計算されるベクトルの第4成分として求めることができます．

$\displaystyle \begin{equation} \begin{pmatrix} 1 & 1 & 1 & 1 \\ 1 & 0 & 0 & 0 \\ 0 & 1 & 0 & 0 \\ 0 & 0 & 1 & 0 \\ \end{pmatrix}^n \begin{pmatrix} 1 \\ 0 \\ 0 \\ 0 \end{pmatrix} \end{equation}$

*1:行列との関係を観察しやすそうだったので，フィボナッチ数列ではなくトリボナッチ数列を中心に考えます．