母関数

はじめに次の例題を考えてみよう。

【例題1】
モールス信号は、「・」（トン）と「−」（ツー）の２種類の文字を数文字連ねて作られる。8文字以内の信号は何種類作ることが可能か。---

(解) 1文字の信号が2つ、2文字の信号が$2^{2}$つ、3文字の信号が$2^{3}$つ、…と考えて
　　　$2+2^{2} + 2^{3} + \cdots + 2^{8} =2(2^{8}-1) =510$(通り)■

上は等比数列の和の公式で解けた。 それは
　　　 $ a + ax + ax^{2} + \cdots + ax^{n-1} = \frac{a(x^{n} -1)}{x-1} $
だが、それは次の等式から証明できる。
　　　$1 + x + x^{2} + \cdots + x^{n-1} = \frac{x^{n} -1}{x-1}$
そしてこの等式自体は
　　　$ (x^{n-1} + \cdots + x^{2} + x^{1} + 1)(x-1) = x^{n} -1 $
をかけ算または割り算で導き出せる。
　　　
なお、かけ算・割り算でやるなら、もう少し一般化した公式
　　　$ a^{n-1} + a^{n-2}b + a^{n-3}b^{2} + \cdots + ab^{n-2} + b^{n-1}
= \frac{a^{n} - b^{n}}{a-b} $
をじかに証明することもできる。

---

§2. 等比に似た数列

等比数列の和の公式を導く方法には2つあって、

1. 教科書にある「掛けて、ずらして引いて、割る」という方法
2. 前述したように、式のかけ算・割り算を使うやり方

である。前者の方が簡単そうだが、後者のやり方もまんざら捨てたものではないと思う。
では、次のような等比数列によく似た数列の和の問題は、どう解けばよいだろうか。

【例題2】
和
　　　$S = 1 + 2x + 3x^{2} +4x^{3} + \cdots + nx^{n-1} $
を求めよ。---

(解1) 教科書流の「掛けて、ずらして引いて、割る」でやると、まず$x$を掛けて
　　　$ xS = x + 2x^{2} + 3x^{3} +4x^{4} + \cdots + nx^{n} $
からこの式をずらして引くと
　　　$ (1-x)S = 1 + x + x^{2} + x^{3} +\cdots + x^{n-1} - nx^{n} $
両辺を$1-x$で割って
　　　$ S = \frac{1-x^{n}}{(1-x)^{2}} - \frac{nx^{n}}{1-x} $
を得る。■

(解2) 等比数列の和の公式
　　　$ f(x) = 1 + x + x^{2} + x^{3} +\cdots + x^{n} = \frac{x^{n+1}-1}{x-1} $
を微分して
　　　$\begin{eqnarray}
S & = & f'(x) \nonumber \\
& = & \frac{nx^{n+1} - (n+1)x^{n}+1}{(x-1)^{2}}
\end{eqnarray}$
を得る。■

(解2)は、母関数(generating function)のアイデアに近い。このアイデアを使った解法をもう一つ示す。

【例題3】
和
　　　$ 1 \cdot 2 + 2 \cdot 3 + 3 \cdot 4 + \cdots + (n-1)n $
を求めよ。---

(解1) 先述の$S = \frac{nx^{n+1} - (n+1)x^{n}+1}{(x-1)^{2}}$をもう一度微分(等比の和$f(x)$の2階微分になる)すると、次の式を得る。
　　　$\begin{eqnarray*}
f''(x) & = & 1 \cdot 2 + 2 \cdot 3x + 3 \cdot 4 x^{2} + \cdots +
(n-1)nx^{n-2} \\
& = &
\frac{(n^{2}-n)x^{n+1} -2(n^{2}-1)x^{n} + (n^{2}+n)x^{n-1} -2}
{(x-1)^{3}}
\end{eqnarray*}$
あとは、ここに$x=1$を代入すればよいようなものだが、それだと$0/0$になってしまう。そこでロピタルの定理を使う。それも3回使うことによって、
　　　$ \displaystyle \lim_{x \rightarrow 1} f''(x) = \frac{n(n+1)(n-1)}{3} $
となる。■

(解2) これは「差分と和分」のページで紹介したやり方だが、
　　　$ \displaystyle \sum_{k=0}^{n-1} k^{[2]} = \frac{1}{3} n^{[3]} $
で、$n$のかわりに$n+1$とおいて
　　　$ \displaystyle \sum_{k=0}^{n} k(k-1) = \frac{1}{3}n(n+1)(n-1) $
である。$\sum k^{2} - \sum k$で計算するより簡単だ。■

教科書に載っているこの種の問題は、階乗関数を和分すると明らかなものが多い。

---

§3. 蛇足：ロピタルの定理

ところで、上に出てきたロピタルの定理だが、これを載せていない数IIIの教科書もある。（それでいながら、$y=x \log x$のグラフを書かせたりしている。$x \rightarrow 0$のとき、どうなるのだろうか？）
ロピタルの定理が難しいかといえば、実は当り前の定理である。例えば、2台のクルマの走行距離の比
　　　$ \frac{f(x)}{g(x)} $
は、速度の比に等しいと考えれば、
　　　$ \lim \frac{f(x)}{g(x)} = \lim \frac{f'(x)}{g'(x)} $
である。
ロピタルを使えば、「極限値
　　　$ \displaystyle \lim_{h \rightarrow 0} \frac{f(x+h) - f(x-h)}{h} $
を求めよ」などという問題は、簡単に解けてしまう。

---

§4. 母関数の利用

等差数列の和の公式
　　　$ 1 + 2 + 3 + \cdots + n = \frac{n(n+1)}{2} $
を通常とは異なる方法で証明してみよう。

(証明) 先の等式
　　　$ 1 + 2x + 3x^{2} +4x^{3} + \cdots + nx^{n-1} =
\frac{nx^{n+1} - (n+1)x^{n} + 1}{(x-1)^{2}} $
において、ロピタルの定理を使う。両辺において、$x \rightarrow 1$とする。右辺は、分母・分子を2階微分すると
　　　$ \frac{n(n+1)n x^{n-1}- (n+1)n(n-1) x^{n-2} }{2} $
となり、このあと $x \rightarrow 1$ として、
　　　$ \frac{n(n+1)}{2} $
で、公式が得られる。■

等差数列に関連して、なんとロピタルの定理まで出てきた。個数の処理、自然数の数列の和などというと分離量(離散)だから、連続量の数学である微積分とは無関係のように思える。しかし、実際には極限をとったり微分したりという操作が非常に役に立ち、両者の関連の深いことが分かった。
そこで使われたのが、「母関数」であった。母関数を微分したり、特定の値を代入したりすると、いろいろな公式がでてくるのであった。
教科書で登場するのは、二項定理
　　　$ (x+1)^{n} = x^{n} + _{n}C_{1}x^{n-1} + _{n}C_{2}x^{n-2} +
\cdots + _{n}C_{n-1}x + 1 $
である。$x=1$や$x=-1$を代入して、公式を導く。このとき、二項定理は母関数の役割を果たしている訳である。

母関数の便利なところを例示しておこう。二項分布
　　　$ P(X=k) = _{n}C_{k} p^{k} q^{n-k} , \mbox{　　} p+q=1 $
の期待値や分散を求めるには、次の母関数を使う。
　　　$ \varphi(t)
= \displaystyle \sum_{k=0}^{n} \mbox{ }_{n}C_{k} (pt)^{k} q^{n-k} = (pt + q)^{n} $
両辺をパラメータ$t$で微分して、$t=1$を代入すれば平均
　　　$ E(X) = \displaystyle \sum_{k=0}^{n} k _{n}C_{k} p^{k} q^{n-k} = np $
が得られる。

分散はこうやる。2階微分して
　　　$ \varphi ''(1) =
\displaystyle \sum_{k=0}^{n} k(k-1) _{n}C_{k} p^{k} q^{n-k} = n(n-1)p^{2} $
より
　　　$ E(X(X-1)) = n(n-1)p^{2} $
を求めておいて、
　　　$\begin{eqnarray*}
V(X) & = & E(X^{2}) - E(X)^{2} \\
& = & X(X^{2}-X) + E(X) - E(X)^{2} \\
& = & n(n-1)p^{2} + np - n^{2}p^{2} \\
& = & npq
\end{eqnarray*}$
と分散を計算できる。