16.1 無限級数

厳密でない言い方をすれば、母関数 (generating function) とは次の形をした無限級数 \(F(x)\) を意味する:

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

母関数 \(F(x)\) の \(x^{n}\) の係数を \([x^{n}]F(x)\) と表記する。つまり \([x^{n}]F(x) ::= f_{n}\) と定める。また、上記の \(F(x)\) を「無限列 \((f_{0}, f_{1}, \ldots)\) の母関数」と呼ぶ。

任意の数列 \(f_{0}\), \(f_{1}\), \(\ldots\), \(f_{n}\), \(\ldots\) を母関数の係数が並んだ列とみなせば、その母関数を調べることで数列の振る舞いを解析できる。数え上げ、再帰的定義、プログラミングに関する問題で姿を現す複雑な列の中には、母関数の係数が並んだ列とみなすことで扱いが容易になるものが存在する。

母関数からは係数の列が自明な場合でも目を見張る結果が得られる。例えば、係数を並べた無限列が \((1,1,\ldots)\) である母関数を \(G(x)\) とする。この \(G(x)\) は幾何級数である:

\[ G(x) ::= 1 + x + x^{2} + \cdots + x^{n} + \cdots \tag{16.2}\]

母関数で頻繁に使われる簡単なテクニックを使って \(G(x)\) を表す単純な式を求めてみよう。このアプローチは第 14.1.2 項で説明した摂動法を簡単にしたバージョンである:

\[ \def\arraystretch{1.2}\begin{array}{rl} G(x) &= 1 + x + x^{2} + x^{3} + \cdots + x^{n} + \cdots \\ -xG(x) &= \hphantom{1} - x - x^{2} - x^{3} - \cdots - x^{n} - \cdots \\ \hline G(x) - xG(x) &= 1 \end{array} \]

\(G(x)\) に関して解けば次の等式を得る:

\[ \sum_{n=0}^{\infty} x^{n} ::= G(x) = \frac{1}{1 - x} \tag{16.3}\]

この事実は次のようにも表せる:

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

同じアプローチを使うと、次の関数に等しい単純な式も見つけられる:

\[ N(x) ::= 1 + 2x + 3x^{2} + \cdots + (n + 1) x^{n} + \cdots \tag{16.4}\]

同様の変形から次の等式が分かる:

\[ \def\arraystretch{1.2}\begin{array}{rl} N(x) &= 1 + 2x + 3x^{2} + 4x^{3} + \cdots + (n + 1) x^{n} + \cdots \\ -xN(x) &= \hphantom{1} - \ \ x - 2x^{2} - 3x^{3} - \cdots - \quad \quad \ \ n x^{n} - \cdots \\ \hline N(x) - xN(x) &= 1 + \ \ x + \ \ x^{2} + \ \ x^{3} + \cdots + \hphantom{(n + 1)}x^{n} + \cdots \end{array} \]

\(N(x)\) に関して解けば次を得る:

\[ N(x) ::= \sum_{n=0}^{\infty} (n + 1) x^{n} = \frac{G(x)}{(1 - x)} = \frac{1}{(1 - x)^{2}} \tag{16.5}\]

この事実は次のようにも表せる:

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

16.1.1 収束性は気にしない

等式 \(\text{(16.3)}\), \(\text{(16.5)}\) は数値的には \(|x| < 1\) のときに限って成立し、\(|x| \geq 1\) だといずれも発散する。しかし、母関数を考える文脈では、無限級数は純粋に代数的なオブジェクトと解釈される。つまり等式 \(\text{(16.3)}\), \(\text{(16.5)}\) は代数的理由のみによって成立する記号的恒等式を主張する。実は、母関数の考え方を使うと (\(x = 0\) を除いて) どの点でも収束しない無限級数にも利用価値が生まれる。この話題は章末の第 16.5 節でさらに詳しく触れるので、今は「とりあえず収束は気にしなくていい」と思ってほしい。