16.4 線形再帰方程式の解法

16.4.1 Fibonacci 数列の母関数

Fibonacciフィボナッチ数 \(f_{0}\), \(f_{1}\), \(\ldots\), \(f_{n}\), \(\ldots\) は次の再帰的な規則で定義される:

\[ \begin{aligned} f_{0} &::= 0 \\ f_{1} &::= 1 \\ f_{n} &::= f_{n-1} + f_{n-2} \qquad (n \geq 2) \end{aligned} \]

母関数を使うと、\(f_{n}\) を表す驚くべき閉形式の式を求められる。

Fibonacci 数を並べた無限列 \((f_{0}, f_{1}, \ldots)\) の母関数を \(F(x)\) とする。つまり、次のように定める:

\[ F(x) ::= f_{0} + f_{1}x + f_{2}x^{2} + \cdots + f_{n} x^{n} + \cdots \]

本章の冒頭で示した幾何級数の変形と同様に変形すれば、次の関係を得る:

\[ \def\arraystretch{1.2}\small\begin{array}{rcrcrcrcccrcc} F(x) &=& f_{0} &+& f_{1}x &+& f_{2}x^{2} &+& \cdots &+& f_{n} x^{n} &+& \cdots \\ -x F(x) &=& &-& f_{0}x &-& f_{1}x^{2} &-& \cdots &-& f_{n-1} x^{n} &-& \cdots \\ -x^{2} F(x) &=& & & &-& f_{0}x^{2} &-& \cdots &-& f_{n-2} x^{n} &-& \cdots \\ \hline F(x) (1 - x - x^{2}) &=& f_{0} &+& (f_{1} - f_{0}) x &+& 0x^{2} &+& \cdots &+& 0x^{n} &+& \cdots \\ &=& 0 &+& 1 x &+& 0x^{2} & & & & & & \\ &=& x & & & & & & & & & & \end{array} \]

ここから次の等式が分かる:

\[ F(x) = \frac{x}{1 - x - x^{2}} \]

この関数は第 16.3 節で部分分数分解の例として示した関数と等しい。この事実と等式 \(\text{(16.12)}\) より、Binetビネの公式 (Binet's formula) と呼ばれる関係を得る:

\[ f_{n} = \frac{1}{\sqrt{5}} \left( \left( \frac{1 + \sqrt{5}}{2} \right)^{\!\! n} - \left( \frac{1 - \sqrt{5}}{2} \right)^{\!\! n} \right) \tag{16.14}\]

Fibonacci 数を表す Binet の公式は驚異的であると同時におそらく恐ろしくもあるだろう。等式 \(\text{(16.14)}\) の右辺が常に整数であるかどうかさえ明らかでない。しかし、この公式は非常に有用である。例えば、この公式と高速乗算のアルゴリズムを使うと再帰的定義を使うより効率的に Fibonacci 数を計算できる。また、Fibonacci 数が指数的に大きくなる事実もすぐに分かる。

16.4.2 Hanoi の塔

伝説によると、Hanoiハノイにある寺院には \(3\) 個の棒と \(64\) 枚の異なる大きさの円盤からなる装置がある。それぞれの円盤の中心には穴が開いていて、そこに棒を通すことができる。はるか昔、全ての円盤は一つ目の棒に大きさの順に積み上げられていた。図 \(\text{16.1}\) に示すように、最も大きな円盤が一番下、最も小さな円盤が一番上にあった。

寺の僧侶たちは長い間、次の規則に従いながら全ての円盤を空いている二つの棒のいずれか一方に移動させる作業を絶え間なく続けてきた:

各ステップで許された唯一の操作は「特定の棒の最も上にある円盤を、他の棒に移す」だけである。
任意の円盤の上にそれより大きな円盤を置くことはできない。

例えば、積まれている円盤を全て持ち上げて他の棒に移す操作は正当でない。しかし、これは幸いである: 伝説では、僧侶たちがこの操作を終えると世界が終焉を迎えるとされている！

この問題を Hanoiハノイの塔問題 (tower of Hanoi problem) と呼ぶ。問題の理解を確認するために、\(64\) 個ではなく \(3\) 個の円盤を使ったバージョンの Hanoi の塔問題を \(7\) ステップで解く方法を図 \(\text{16.2}\) に示す。

n = 3 個の円盤を持った Hanoi の塔問題に対する 7 ステップの解法 — 図 16.2\(n = 3\) 個の円盤を持った Hanoi の塔問題に対する \(7\) ステップの解法

この Hanoi の塔問題に関していくつか疑問が思い浮かぶ: 「十分な時間をかければ、僧侶たちは必ず操作を終えられるか？」「世界の終焉までの時間はどれくらいか？」そして最も重要なこととして: 「世界の終焉は期末試験より前に起こるか？」

再帰的な解法

Hanoi の塔問題を再帰的に解くアルゴリズムが存在する。それを説明するために、円盤が \(n\) 個ある Hanoi の塔問題を解くのに必要な最小ステップ数を \(t_{n}\) とする。例えば、少し試行錯誤すれば \(t_{1} = 1\) と \(t_{2} = 3\) が分かる。また、図 \(\text{16.2}\) に示した解法からは \(t_{3} \leq 7\) が分かる。

再帰的なアルゴリズムは次の \(3\) 個のステージからなる。模式図を図 \(\text{16.3}\) に示す。

ステージ \(1\): 円盤が \(n - 1\) 個の Hanoi の塔問題を解くアルゴリズムを使って、左端の棒 (初期位置) にある上から \(n - 1\) 個の円盤を中央の棒に移す。この操作は \(t_{n-1}\) ステップで実行できる。
ステージ \(2\): 最も大きな円盤を左端の棒から右端の棒に移す。この操作は \(1\) ステップで実行できる。
ステージ \(3\): 円盤が \(n - 1\) 個の Hanoi の塔問題を解くアルゴリズムを使って、中央の棒にある \(n - 1\) 個の円盤を右端の棒に移す。この操作は \(t_{n-1}\) ステップで実行できる。

このアルゴリズムからは、\(n\) 個の円盤を他の棒に移すのに必要となる最小ステップ数 \(t_{n}\) が \(t_{n-1} + 1 + t_{n-1} = 2t_{n-1} + 1\) 以下だと分かる。この事実を使えば、様々な高さの塔を移動させるのに必要なステップ数の上界が得られる:

\[ \begin{aligned} t_{3} \leq 2 \cdot t_{2} + 1 = 7 \\ t_{4} \leq 2 \cdot t_{3} + 1 \leq 15 \end{aligned} \]

こうして計算を続けていけば、いずれ \(t_{64}\) の上界も求まる。つまり上記のアルゴリズムは一つ目の質問に答える: 十分な時間があれば、僧侶たちは作業を終えて世界は終焉を迎える。しかしなんとも残念な話だ: ずっと働き通しだったのだから、ハイタッチでもしてハンバーガーとアイスクリームを食べに行きたいだろうに ── 作業が完了した瞬間に世界は終わってしまう。

再帰方程式を見つける

ここまでの議論は \(64\) 枚の円盤からなる塔を移動させるのに必要な最小ステップ数に上界が存在することを示しただけで、正確なステップ数は分からない。もしかしたら、この問題について太古から考え続けてきた僧侶たちが優れたアルゴリズムを考案しているかもしれない。

しかし、私たちにとっては幸いなことに、先ほど説明したものより優れたアルゴリズムは存在しない。理由は次の通りである: あるステップで、僧侶たちは最も大きい円盤を異なる棒に移動させる。このためには、残りの \(n - 1\) 枚の円盤は全て移動に関係しない唯一の棒に刺さっている必要がある。\(n - 1\) 枚の円盤をその状態に移動させるには最低で \(t_{n-1}\) ステップが必要であり、最も大きい円盤を移動させた後に \(n - 1\) 枚の円盤をその上に移動させるのにも最低で \(t_{n-1}\) が必要になる。

よって、\(n\) 枚の円盤を使う Hanoi の塔問題に対する任意の解法は最低でも \(2 t_{n-1} + 1\) ステップを必要とする。一方で上記のアルゴリズムはちょうど \(2 t_{n-1} + 1\) ステップで実行可能なので、円盤が \(n\) 枚の Hanoi の塔問題を解くのに最低限必要なステップ数 \(t_{n}\) は次の関係を満たすと結論できる:

\[ \begin{aligned} t_{0} &= 0 \\ t_{n} &= 2t_{n-1} + 1 \quad (n \geq 1) \end{aligned} \]

再帰方程式を解く

\(t_{n}\) を表す式は母関数を使うと見つけられる。無限列 \((t_{0}, t_{1}, \ldots)\) の母関数を \(T(x)\) とする。つまり、次のように定める:

\[ T(x) ::= t_{0} + t_{1} x + t_{2} x^{2} + \cdots + t_{n} x^{n} + \cdots \]

Fibonacci 数の再帰方程式と同様に変形すれば、次の関係を得る:

\[ \def\arraystretch{1.2}\small\begin{array}{rcrcrcrcccrcc} T(x) &=& t_{0} &+& t_{1} x &+& \cdots &+& t_{n} x^{n} &+& \cdots \\ -2x T(x) &=& &-& 2t_{0} x &-& \cdots &-& 2t_{n-1} x^{n} &-& \cdots \\ -1/(1-x) &=& -1 &-& 1 x &-& \cdots &-& 1 x^{n} &-& \cdots \\ \hline T(x) (1 - 2x) - 1/(1-x) &=& t_{0} -1 &+& 0 x &+& \cdots &+& 0 x^{n} &+& \cdots \\ &=& -1 & \end{array} \]

ここから次の等式が分かる:

\[ \begin{aligned} T(x) (1 - 2x) &= \frac{1}{1-x} - 1 = \frac{x}{1 - x} \\[10pt] T(x) &= \frac{x}{(1 - 2x)(1 - x)} \end{aligned} \]

続いて、この関数の部分分数分解を求めよう。ある定数 \(c_{1}\), \(c_{2}\) を使って次のように表せたと仮定する:

\[ \frac{x}{(1 - 2x)(1 - x)} = \frac{c_{1}}{1 - 2x} + \frac{c_{2}}{1 - x} \]

左辺の分母を両辺に乗じれば次の等式を得る:

\[ x = c_{1} (1 - x) + c_{2} (1 - 2x) \]

\(x = 1/2\) を代入すれば \(c_{1} = 1\) が分かり、\(x = 1\) を代入すれば \(c_{2} = -1\) が分かる。よって、次の等式が成り立つ:

\[ T(x) = \frac{1}{1 - 2x} - \frac{1}{1 - x} \]

これでようやく、\(n\) 個の円盤を使う Hanoi の塔問題を解くのに必要なステップ数を表す単純な式が判明した:

\[ t_{n} = [x^{n}]T(x) = [x^{n}] \left( \frac{1}{1 - 2x} \right) - [x^{n}] \left( \frac{1}{1 - x} \right) = 2^{n} - 1 \]

16.4.3 一般的な線形再帰方程式の解法

定数 \(c_{i} \in \mathbb{C}\) を使って次の形で表せる方程式を、非斉次項 (inhomogeneous term) が \(h(n)\) の \(d\) 次線形再帰方程式 (degree \(d\) linear recurrence) と呼ぶ:

\[ f(n) = c_{1} f(n - 1) + c_{2} f(n - 2) + \cdots + c_{d} f(n - d) + h(n) \tag{16.15}\]

これまでに説明してきた手法を使えば、様々な種類の非斉次項を持った線形再帰方程式の解を求められる。特に、斉次項そのものが多項式の比で表せる母関数を持つときは、この手法を使うと母関数 \(f(0) + f(1)x + f(2)x^{2} + \cdots\) を定義する多項式の比が得られる。ここからさらに部分分数分解を使えば、\(n^{k}\alpha^{n}\) の形をした項の線形結合として \(f(n)\) を表せる。ここで \(k\) は \(d\) 以下の非負整数、\(\alpha\) は分母の多項式の根の逆数である。問題 16.14, 問題 16.15, 問題 16.18, 問題 16.19 に例を示してある。