数列と母関数
前頁では母関数に関するイロハのイを紹介した。ここでは数列と母関数の関係について更に詳しく見ていく。
これまで散々、母関数の収束性は気にしない、と述べてきたが、ある母関数を閉じた式で表示するためにはそもそも冪級数自体が収束する必要がある。一般に次の事実が知られている。
「ある数列の通常型母関数が有理式で表されるための必要十分条件は、その数列が線型漸化式を持つことである」
「有理式」というのはここで言う「閉じた式（closed form）」のことで、$\small \dfrac{x}{(1-x)^2}$ といった多項式の比で表せる式を指している。「線型漸化式」というのは簡単に言えば$$a_{n+2}=a_{n+1}+a_{n}$$のような１次の項（項数は有限個なら幾ら有っても良い）から成る漸化式（これはフィボナッチ数列）のことであり、$$a_{n+1}={a_{n}}^2-a_{n}+1$$のような漸化式（これはシルベスター数列）は「非線形」である。例えば $a_n=2^n-1$ で定義されている数列（このように表される数をメルセンヌ数という）は$$a_{n+1}=2a_{n}+1$$という線形な漸化式をもつから、母関数は閉じた式で表すことができる。実際、メルセンヌ数の列の母関数は $\small f(x)=\dfrac{x}{(1-x)(1-2x)}$ となる。一方で $a_n=2^{2^n}+1$ で定義されている数列（このように表される数をフェルマー数という）は$$a_{n+1}={a_{n}}^2-2a_{n}+2$$という非線形な漸化式をもつため、母関数は閉じた表示をもたない。
母関数の種類
前頁では専ら「通常型母関数」（Ordinary Generating Function：$\text{O.g.f.}$）を紹介したが、母関数の仲間には他にも色々な種類がある。ここではもう一種類だけ紹介しておこう。
数列$\{a_n\}$（$n=0,1,2,\cdots$）に対して、形式的冪級数$$\small \displaystyle \sum_{k=0}^{\infty} a_k \dfrac{x^k}{k!}=a_0\dfrac{1}{0!}+a_1\dfrac{x}{1!}+a_2\dfrac{x^2}{2!}+a_3\dfrac{x^3}{3!}+\cdots \tag{1.7}$$を数列$\{a_n\}$の「指数型母関数」（Exponential Generating Function：$\text{E.g.f.}$）という。これにより、通常型母関数では閉じた式にならないような収束半径の大きな数列に対して、母関数を対応させることができる。例えば $a_n=n!$ で定義される数列（階乗）は通常型母関数が閉じた表示をもたないが、指数型母関数は $\dfrac{1}{1-x}$ となる。これにより、すべての項が$1$からなる数列の通常型母関数と同じように扱うことができる。
また、明確な漸化式が存在しない数列や特殊な漸化式をもつ数列に対しても指数型母関数が定義できる場合がある。以下に指数型母関数の例を挙げる。
《指数型母関数の例》
（例）モンモール数（完全順列の総数）：一般項は $M_n=\displaystyle \sum_{k=0}^{n} \dfrac{(-1)^k n!}{k!}$ $$\text{E.g.f.}：f(x)=\dfrac{e^{-x}}{1-x}$$
（例）ベル数（$n$個の要素をグループ化する方法の総数）：漸化式は $B_0=1,B_{n+1}=\displaystyle \sum_{k=0}^{n} {}_n\mathrm{C}_k B_k$ $$\text{E.g.f.}：f(x)=e^{e^x-1}$$
（例）ベルヌーイ数：漸化式は $B_0=1,B_{n+1}=-\dfrac{1}{n+2}\displaystyle \sum_{k=0}^{n} {}_{n+2}\mathrm{C}_k B_k$ $$\text{E.g.f.}：f(x)=\dfrac{x}{e^x-1}$$
要するに数列$\{a_n\}$に対して新たな数列$\left\{\dfrac{a_n}{n!}\right\}$の通常型母関数を考えているのが指数型母関数ということになる。ここでは指数型母関数の簡単な紹介に留めておく。
通常型母関数
さて、通常型母関数の話に戻ろう。前頁では自然数の冪$n^k$の母関数が微分的操作により次々と求められることを理解した。高校数学では数学Ⅱの分野に当たる内容だが、数列を把握する際に必ずといっていいほど登場する数列、「和」について調べてみよう。ここで言う和とは勿論「部分和」である。以下、便宜を考えて母関数の定数項$a_0$について $a_0=0$ と定めておく。
$a_n=1 \ (n=1,2,3,\dots)$ で定められる数列の母関数は $\dfrac{x}{1-x}$ である。この数列の和は新たな数列 $1,2,3,4,\dots$ を成す。これを$S_n$とすると、$S_n$の母関数は$$\dfrac{x}{(1-x)^2}$$となる（∵前頁$(1.5)$式より）。
更に$S_n$の和を考えてみよう。$S_n=n \ (n=1,2,3,\dots)$ で定められる数列の母関数は $\dfrac{x}{(1-x)^2}$ であり、$S_n$の和は新たな数列 $1,3,6,10,\dots$ を成す。これを$T_n$とすると、$T_n$の母関数は$$\dfrac{x}{(1-x)^3}$$となる。同様に$T_n$の和を$U_n$とすれば、この母関数は$$\dfrac{x}{(1-x)^4}$$となる。
さて、ここでこの母関数のカラクリを説明しよう。一見してわかる通り、和の母関数は $\dfrac{1}{1-x}$ を元の数列の母関数に乗じるだけで次々と得られている。$\dfrac{1}{1-x}$ は元々$$1+x+x^2+x^3+\cdots$$という形の冪級数であった。ここで次の掛け算を考える。$$\small \begin{align}&\ \ \ \ \ (a_0+a_1 x+a_2 x^2+a_3 x^3+\cdots)(1+x+x^2+x^3+\cdots) \\ &=a_0+(a_0+a_1)x+(a_0+a_1+a_2)x^2+(a_0+a_1+a_2+a_3)x^3+\cdots \end{align}$$見ての通り、和の数列が係数となっている冪級数が現れている。これが次から次へと和の母関数を生じるカラクリだったのである。このように $\dfrac{1}{1-x}$ を乗じることによって和の母関数が得られるため、$\dfrac{1}{1-x}$ は「和分作用素」と呼ばれる。
和分作用素の適用例
この和分作用素を用いて平方数の総和公式を導出してみよう。前頁で記した通り、$$\begin{align} \displaystyle \sum_{k=1}^{\infty} k^2 x^k &=x+4x^2+9x^3+\cdots \\ &=\dfrac{x(x+1)}{(1-x)^3} \end{align}$$である。これに和分作用素 $\dfrac{1}{1-x}$ を乗じると、平方数の総和を係数に持つ母関数は$$\dfrac{x(x+1)}{(1-x)^4} \tag{1.8}$$となる。ここで負の指数に関する二項展開を考える必要がある。結論から述べると一般に$0$以上の整数$n$に対して$$\color{red}{\dfrac{1}{(1-x)^{n+1}}=\displaystyle \sum_{k=0}^{\infty} {}_{n+k}\mathrm{C}_k x^k} \tag{1.9}$$が成り立つのだが、これは左辺のマクローリン展開から容易に示される（$(1.9)$式は母関数から係数を取り出す際に重宝する重要な式である）。$(1.9)$式を用いると、$(1.8)$式における$x^n$の係数は$$\dfrac{x(x+1)}{(1-x)^4}=\dfrac{x^2}{(1-x)^4}+\dfrac{x}{(1-x)^4}$$と考えることにより、$${}_{n+1}\mathrm{C}_3+{}_{n+2}\mathrm{C}_3$$で与えられることが分かる（項番号に注意せよ）。
これを計算してやると、めでたく$$\dfrac{1}{6}n(n+1)(2n+1)$$を得る。これより、$$\small 1+4+9+\cdots+n^2=\dfrac{1}{6}n(n+1)(2n+1)$$が導かれた。
このようにある数列の和を求める際に母関数が活躍する場合がある。勿論、平方数の総和公式を導出するのに母関数を用いるというのは大袈裟ではあるが、利用例としては理解しやすいであろう。
母関数の平方＝畳み込み和の母関数
次に母関数$f(x)$を$2$乗してみる。するとまた面白い数列が得られる。
$\small \begin{align} \{f(x)\}^2&={a_0}^2+(a_0 a_1+a_1 a_0)x+(a_0 a_2+a_1 a_1+a_2 a_0)x^2+\cdots \\ &=\displaystyle \sum_{k=0}^{\infty}\displaystyle \sum_{j=0}^{k} a_j a_{k-j}x^k \tag{1.10} \end{align}$
新しく $\displaystyle \sum_{j=0}^{k} a_j a_{k-j}$ で定義される数列を数列$\{a_n\}$の「畳み込み和」という。全く同様の構造により数列$a_n$の母関数$f(x)$と数列$b_n$の母関数$g(x)$の積は、畳み込み和 $\displaystyle \sum_{j=0}^{k} a_j b_{k-j}$ を与える。これにより確率や期待値などの計算が関数の力を借りることで実行できるようになる。
次頁ではこれらの導入を踏まえ、実際の計算に母関数を応用してみる。