■ - ナルト世界の謎を紐解く

今回一般的に求めて、次回具体的に何通りか考察します。
【陽と陰、ＮとＳ、ナルトとサスケ】*1に、
週末が忙しいと書きましたが、訂正。
正しくは　土、日〜月にかけて　です。
そう、ちょうど感想を書くとき(T_T)なのです。
というわけで、この考察の続きも次の感想も遅れると思いますが
どうかどうかご容赦ください。m(_ _)m

３．多重影分身の陣（３）

前回の記事*2より

ナルト本体（＊）、仙人モード影分身（●）、通常影分身（○）
で空間的にフォーメーションを組む。
仙人モード影分身●や通常影分身○は同じ質のものを
複数つくることができる。
このとき以下の２条件を満たすものとする。

　(1) 風遁・螺旋手裏剣のため、本体の隣に補助として
　　　仙人モード影分身●を２体配置する。
　(2) 遊撃のために仙人モード影分身●を通常影分身○に混ぜるが、
　　　このとき疎＜まば＞らになるように●を配置する。
　　　ただし○は隣り合って配置されていてもよい。

隣り合う２体とは左右、上下、前後方向で隣り合う一番近くにある２体を選ぶ。
このとき上下、左右、前後方向ではどの配置においても微妙でも距離が違い、
必ず近い順に２体が決まるものとする。
また疎らに配置するとは、左右、上下、前後方向どれとも隣り合わないこととする。
すなわち●の左右、上下、前後方向には○が配置され、
●同士では決して隣り合わないものとする。

という条件のもと、
ｎ人でのフォーメーションは何パターンあるかは、

左から一列に順番に○、●のみ重複を許し、○、●、＊をｎ個並べる並べ方。
ただし●は｛…○、●、○…｝の順に並び、＊は｛…●、＊、●…｝の順に並ぶ。

というわけでした。

さてここでk番目（1≦k≦n）に＊を並べる並べ方を $a_k$ 通りとします。
また同様にk番目に●、○が来る並べ方を $b_k$ 、 $c_k$ 通りとします。
そうすると、

$\overbrace{\cdots \bullet}^{1 \cdots {k-1}} \ast \underbrace{\bullet \cdots}_{{k+1} \cdots n}$

のようになって、左から数えてk-1番目に●が、
また右から数えてn-k番目に●が来るように並べる並べ方なので、

$a_k=b_{k-1} \cdot b_{n-k}$

$(1)$

となります。 $b_k$ および $c_k$ には以下の図より、

$\begin{eqnarray} & n-1 & n \\ \cdots & \circ & \bullet \end{array}$
$b_k=c_{k-1}$

$\begin{eqnarray} & n-1 & n \\ \cdots & \bullet & \circ \\ \cdots & \circ & \end{array}$
$c_k=b_{k-1}+c_{k-1}$

したがって、以下の漸化式を得ます。

$b_{k+1}=b_k+b_{k-1}$

$(2)$

また最終的に求めるものは、

$S_n=\sum_{k=1}^n a_k$

$(3)$

となります。

４．多重影分身の陣（４）〜フィボナッチ数列

ここで
$\{ b_1=1 \\ b_2=1$
はすぐに分かり、
式 $(2)$ はフィボナッチ数列と呼ばれるもので、
前の２項を足したもので新しい項ができます。
この漸化式の特性方程式
$t^2-t-1=0$
の２解をα、β（α＜β）とします。このとき、

$\{ \alpha=\frac{1-\sqrt{5}}{2} \\ \beta=\frac{1+\sqrt{5}}{2}$

(2.1)

$\beta - \alpha=\sqrt{5}$

(2.2)

$\alpha \beta=-1$

(2.3)

となります。特性方程式は
$(t-\alpha)(t-\beta)=0 \\ \qquad (t^2-\alpha t)=\beta(t-\alpha t)$
と書けます。またαとβを入れ替えても等価なので、

$\{ b_{k+1}-\alpha b_k=\beta(b_{k}-\alpha b_{k-1})=\cdots={\beta}^{k-1}(b_2 - \alpha b_1) \\ b_{k+1}-\beta b_k=\alpha(b_{k}-\beta b_{k-1})=\cdots={\alpha}^{k-1}(b_2 - \beta b_1)$

(2.4)

したがって $b_{k+1}$ を消去して、

$b_k=\frac{{\beta}^{k-1}-{\alpha}^{k-1}}{\beta - \alpha}b_2-\frac{\alpha \beta({\beta}^{k-2}-{\alpha}^{k-2})}{\beta - \alpha}b_1$

(2.5)

よって(2.2)式〜(2.5)式より

$b_k=\frac{1}{\sqrt{5}} \{ (\frac{1+\sqrt{5}}{2})^k - (\frac{1-\sqrt{5}}{2})^k \}$

(2.6)

なお、
$\frac{3+\sqrt{5}}{2}=(\frac{1+\sqrt{5}}{2})^2$
である点に注意します。

５．多重影分身の陣（５）〜対称式の和

式(1)、(2.6)から $a_k$ を求めることができて、

$\begin{eqnarray} a_k &=& b_{k-1} \cdot b_{n-k} \\ &=& \frac{1}{5} \{ (\frac{1+\sqrt{5}}{2})^{k-1}-(\frac{1-\sqrt{5}}{2})^{k-1} \} \{ (\frac{1+\sqrt{5}}{2})^{n-k} -(\frac{1-\sqrt{5}}{2})^{n-k} \} \\ &=& \frac{1}{5} \{ (\frac{1+\sqrt{5}}{2})^{n-1}+(\frac{1-\sqrt{5}}{2})^{n-1} \\ &{}&\qquad \qquad \qquad-(\frac{1+\sqrt{5}}{2})^{k-1}(\frac{1-\sqrt{5}}{2})^{n-k}-(\frac{1+\sqrt{5}}{2})^{n-k}(\frac{1-\sqrt{5}}{2})^{k-1} \}\end{array}$

(1.1)

したがって式(3)を考えればよいことになりますが、ここでα、βを用いて

$S_n=\frac{n}{5}({\beta}^{n-1}+{\alpha}^{n-1})-\frac{1}{5}(\sum_{k=1}^n {\alpha}^{k-1}{\beta}^{n-k}+\sum_{k=1}^n {\beta}^{k-1}{\alpha}^{n-k})$

(3.1)

となります。

ここで

$\{ \sum_{k=1}^n {\alpha}^{k-1}{\beta}^{n-k} \\ \sum_{k=1}^n {\beta}^{k-1}{\alpha}^{n-k}$

を考えます。
これらは対称式であり、αとβを入れ替えても等価です。
そこで、
$T(\alpha,\beta)=\sum_{k=1}^n {\alpha}^{k-1}{\beta}^{n-k}$
とすると、
$\begin{eqnarray} &T(\alpha,\beta)& = {\beta}^{n-1}+{\alpha}{\beta}^{n-2}+{\alpha}^{2}{\beta}^{n-3}+\cdots+{\alpha}^{n-3}{\beta}^{2}+{\alpha}^{n-2}{\beta}+{\alpha}^{n-1} \\ & \alpha T(\alpha,\beta)&=\alpha {\beta}^{n-1}+{\alpha}^2{\beta}^{n-2}+{\alpha}^{3}{\beta}^{n-3}+\cdots+{\alpha}^{n-2}{\beta}^{2}+{\alpha}^{n-1}{\beta}+{\alpha}^{n} \\ &\beta T(\alpha,\beta)&={\beta}^{n}+{\alpha}{\beta}^{n-1}+{\alpha}^{2}{\beta}^{n-2}+\cdots+{\alpha}^{n-3}{\beta}^{3}+{\alpha}^{n-2}{\beta}^2+{\alpha}^{n-1} \beta \end{array}$
であるから、
$(\beta - \alpha)T(\alpha,\beta)={\beta}^n - {\alpha}^n$
すなわち

$T(\alpha,\beta)=\frac{{\beta}^n - {\alpha}^n}{\beta - \alpha}$

(3.2)

よって(3.1)式および(3.2)式より

$S_n=\frac{n}{5}\{ (\frac{1+\sqrt{5}}{2})^{n-1}+(\frac{1-\sqrt{5}}{2})^{n-1} \} -\frac{2 \sqrt{5}}{25}\{ (\frac{1+\sqrt{5}}{2})^n-(\frac{1+\sqrt{5}}{2})^n \}$

(3.3)

です。

*1:【陽と陰、ＮとＳ、ナルトとサスケ】

*2:【フォーメーション論１　ナルトの多重影分身(i)】