戻る 次へ
母関数とは
数列を解析する方法には様々なものがあるが、中には多項式、特にこの場合は「『形式的な』冪級数」を利用するものがある。
例えば次のような級数を考える。$$\lim_{n \to \infty} \sum_{k=0}^n x^k$$これを便宜的に$\displaystyle \sum_{k=0}^{\infty} x^k$と書くことにする。この級数の各項を書き下すと次のようになる。$$1+x+x^2+x^3+\cdots$$ここで $|x|<1$ を仮定するとこの（無限）級数は次のような「閉じた式」で書き表すことができる。$$\dfrac{1}{1-x}$$これは事実、$|x|<1$ という制約の下でしか許容されない表示だが、これを全実数まで拡大して、$$\small 1+x+x^2+x^3+\cdots=\dfrac{1}{1-x}$$と「形式的に」等号で結んでみることにする。実はこれが母関数の正体なのである。
母関数の定義
一般に、数列$\{a_n\}$（$n=0,1,2,\cdots$）に対して、（ときに無限次の）多項式$$\small \displaystyle \sum_{k=0}^{\infty} a_k x^k=a_0+a_1 x+a_2 x^2+a_3 x^3+\cdots \tag{1.1}$$を数列$\{a_n\}$の母関数（若しくは生成関数：generating function）という。また、特にこれを「通常型母関数」と呼称する。数列の項をgenerate（生み出す）するから「generating function」という。そう考えるとなるほど、母関数の「母」という訳語も理に適っている（これに対して「父関数」というのもありそうなものだが、”generating function”という英語には元々”mother”の”m”の字も無い）。
要するに、$x^n$の係数が$a_n$になっているような冪級数を「母関数」と呼んでいる。無限数列なら無限に項が続くし、有限数列なら単なる多項式となるが、ここではほとんどの場合、数列が無限数列であるとして話を進めていく。
母関数というと単にこれだけのことなのだが、多項式を組み合わせただけで何が便利なものか、かえって数列が複雑にならないか、と気を揉む人も出てくるかもしれない。ここでは関数の収束性を取り敢えず一端脇に置いておき、各種母関数を「閉じた式」で書き表すことを目指したい。母関数においては$x$は脇役で、あくまでも「係数」が主役であることをよく理解しておこう。
「閉じた式」というのは大雑把に言えばシグマ記号（和の記号）やドット（「$\cdots$」などの記号）を使わない式、或いは漸化式や微分方程式などで表されない式のことを指している（「閉じた式」の対義語として「開いた式」というのもありそうなものだが、寡聞にして聞いたことが無い）。先程の例だと公比が$x$の無限級数として直ちに導かれるが、一般の数列の母関数を求める公式のようなものは知られていない。ここでは簡単な数列の母関数を考えてみよう。
母関数の例
以下、数列$\{a_n\}$に対する母関数を$f(x)$とする。
$a_0=1$、$a_n=1 \ (n=1,2,3,\dots)$ のとき、$$\small \begin{align} f(x) &=\displaystyle \sum_{k=0}^{\infty} x^k \\ &=1+x+x^2+x^3+\cdots \\ &=\dfrac{1}{1-x} \tag{1.2} \end{align}$$
定数項が煩わしければ $a_0=0$、$a_n=1 \ (n=1,2,3,\dots)$ として、（初項の番号に注意！）$$\small \begin{align} f(x) &=\displaystyle \sum_{\color{red}{k=1}}^{\infty} x^k \\ &=x+x^2+x^3+\cdots \\ &=\dfrac{x}{1-x} \tag{1.3} \end{align}$$としてもよい。これは明らかに$(1.2)$式に$x$を乗じた式であり、数列の項番号が１つ進んだ母関数を与えていることが分かる。
$f(x)$の係数となる数列の各項の添え字（index）の書き方には何通りか流儀があり、$a_0$ではなく$a_1$を初項とする場合もある。例えば次のような場合を考えれば納得しやすいかもしれない。
$a_0=1$、$a_n=n \ (n=1,2,3,\dots)$ のとき、$$\small \begin{align} f(x) &=1+\displaystyle \sum_{k=1}^{\infty} k x^k \\ &=1+x+2x^2+3x^3+\cdots \\ &=1+\dfrac{x}{(1-x)^2} \\ &=\dfrac{1-x+x^2}{(1-x)^2} \tag{1.4} \end{align}$$となるが、$a_0=0$、$a_n=n \ (n=1,2,3,\dots)$ とすれば、$$\small \begin{align} f(x) &=\displaystyle \sum_{k=1}^{\infty} k x^k \\ &=x+2x^2+3x^3+\cdots \\ &=\dfrac{x}{(1-x)^2} \tag{1.5} \end{align}$$となって幾分すっきりした印象を受ける。このように、$a_0=0$ とする、つまり$a_0$という定数項を除き、$a_1$を初項とした方が自然な場合もある。$(1.4)$や$(1.5)$の計算方法はごく基本的な内容であるが、公比を乗じたものと差を取って和を求める方法の他に、次のように微分を利用する方法がある。$$\small \begin{align} f(x) &=\displaystyle \sum_{k=1}^{\infty} k x^k \\ &=x+2x^2+3x^3+\cdots \\ &=x(1+2x+3x^2+\cdots) \\ &=x \cdot \dfrac{d}{dx}(1+x+x^2+x^3+\cdots ) \\ &=x \cdot \dfrac{d}{dx}\left(\dfrac{1}{1-x}\right) \tag*{(∵ (1.2))} \\ &=\dfrac{x}{(1-x)^2} \end{align}$$この方法を用いれば$n^2$や$n^3$を係数とする母関数を幾らでも求めることができる。以下に$10$乗までの冪の母関数について提示しておこう。
$\begin{align} f_0(x) &=\displaystyle \sum_{k=1}^{\infty} x^k \\ &=x+x^2+x^3+\cdots \\ &=\dfrac{x}{1-x} \end{align}$
$\begin{align} f_1(x) &=\displaystyle \sum_{k=1}^{\infty} k x^k \\ &=x+2x^2+3x^3+\cdots \\ &=\dfrac{x}{(1-x)^2} \end{align}$
$\begin{align} f_2(x) &=\displaystyle \sum_{k=1}^{\infty} k^2 x^k \\ &=x+4x^2+9x^3+\cdots \\ &=\dfrac{x(x+1)}{(1-x)^3} \end{align}$
$\begin{align} f_3(x) &=\displaystyle \sum_{k=1}^{\infty} k^3 x^k \\ &=x+8x^2+27x^3+\cdots \\ &=\dfrac{x(x^2+4x+1)}{(1-x)^4} \end{align}$
$\begin{align} f_4(x) &=\displaystyle \sum_{k=1}^{\infty} k^4 x^k \\ &=x+16x^2+81x^3+\cdots \\ &=\dfrac{x(x^3+11x^2+11x+1)}{(1-x)^5} \end{align}$
以下同様に、
$\small f_5(x)=\dfrac{x(x^4+26x^3+66x^2+26x+1)}{(1-x)^6}$
$\small f_6(x)=\dfrac{x(x^5+57x^4+302x^3+302x^2+57x+1)}{(1-x)^7}$
$\small f_7(x)=\dfrac{x(x^6+120x^5+1191x^4+2416x^3+1191x^2+120x+1)}{(1-x)^8}$
$\small \begin{align} f_8(x)=\dfrac{x}{(1-x)^9}(x^7 &+247x^6+4293x^5+15619x^4 \\ &+15619x^3+4293x^2+247x+1) \end{align}$
$\small \begin{align} f_9(x)=\dfrac{x}{(1-x)^{10}}(x^8 &+502x^7+14608x^6+88234x^5 \\ &+156190x^4+88234x^3+14608x^2+502x+1) \end{align}$
$\small \begin{align} f_{10}(x)=\dfrac{x}{(1-x)^{11}}(x^9 &+1013x^8 +47840x^7+455192x^6+1310354x^5 \\ &+1310354x^4+455192x^3+47840x^2+1013x+1) \end{align}$
という具合である。これらの級数が実際に冪を係数にもつことはマクローリン展開によって確かめることができる。ある次数の$x$について、係数の一般項を求めてみるのも面白い。興味を持たれた方は是非チャレンジしてみて欲しい。
以上、$n^k$型の数列の母関数を見てきた。これらは無限数列であるが、有限数列の例も身近に存在する。例えば二項係数 ${}_n\mathrm{C}_k$ は $f(x)=(1+x)^n$ における$x^k$の係数として得られる。つまり、二項係数 ${}_n\mathrm{C}_k$ の母関数は$$f(x)=(1+x)^n$$である。式に直せば$$\small \begin{align} f(x) &=\displaystyle \sum_{k=0}^{n} {}_n\mathrm{C}_k x^k \\ &={}_n\mathrm{C}_0+{}_n\mathrm{C}_1 x+{}_n\mathrm{C}_2 x^2+\cdots+{}_n\mathrm{C}_n x^n \\ &=(1+x)^n \tag{1.6} \end{align}$$といった具合である。
この$f(x)$に様々な値を代入することによって多様な関係式を導くことができる。試しに $x=1$ としてみると次の関係式が導かれる。$$\small {}_n\mathrm{C}_0+{}_n\mathrm{C}_1+{}_n\mathrm{C}_2+\cdots+{}_n\mathrm{C}_n=2^n \tag{1.6.1} $$また、$x=-1$ としてみると、$$\small {}_n\mathrm{C}_0-{}_n\mathrm{C}_1+{}_n\mathrm{C}_2-\cdots+(-1)^n{}_n\mathrm{C}_n=0 \tag{1.6.2}$$となるし、$1$の3乗根 $\omega$、${\omega}^2$ を代入して$$\small {}_n\mathrm{C}_0+{}_n\mathrm{C}_3+{}_n\mathrm{C}_6+\cdots=\dfrac{1}{3}\{2^n+(-{\omega}^2)^n+(-{\omega})^n\} \tag{1.6.3}$$を導いたり、4乗根 $\pm 1,\pm i$ を代入して$$\small {}_n\mathrm{C}_0+{}_n\mathrm{C}_4+{}_n\mathrm{C}_8+\cdots=\dfrac{1}{4}\{2^n+(1+i)^n+(1-i)^n\} \tag{1.6.4}$$を導いたりできる。
ともかく、収束性を論じず、数列の各項に次数が対応する冪級数を形式的に考えるのが、この母関数というものである。次頁では更に数列との詳しい関係を見ていこう。