§B4.17母関数入門

最終更新

数列の各項を係数として一つの形式的なべき級数へまとめ、係数の比較によって場合の数と漸化式を扱います。xxは値を代入する変数ではなく、次数ごとの係数を区別する不定元として扱います。

1 定義

定義 1.1 (通常母関数). 数列(an)n≥0(a_n)_{n\ge0}に対して、形式的なべき級数

A(x)=∑n≥0anxnA(x)=\sum_{n\ge0}a_nx^n

を数列の通常母関数といいます。本記事では収束を仮定せず、同じ次数の係数を比較します。

例 1.2. 赤玉を0個から2個、青玉を0個から3個選ぶとします。合計nn個を選ぶ方法の個数は

(1+x+x2)(1+x+x2+x3)(1+x+x^2)(1+x+x^2+x^3)

のxnx^nの係数です。各因子で選んだ次数の和が合計個数を表します。

2 フィボナッチ数列の母関数

フィボナッチ数列をF0=0,F1=1,Fn+2=Fn+1+FnF_0=0,F_1=1,F_{n+2}=F_{n+1}+F_nで定めます。

定理 2.1. 形式的なべき級数F(x)=∑n≥0FnxnF(x)=\sum_{n\ge0}F_nx^nは

F(x)=x1−x−x2F(x)=\frac{x}{1-x-x^2}

を満たします。

証明. 漸化式へxn+2x^{n+2}を掛けてn≥0n\ge0について足すと、

∑n≥0Fn+2xn+2=x∑n≥0Fn+1xn+1+x2∑n≥0Fnxn\sum_{n\ge0}F_{n+2}x^{n+2} =x\sum_{n\ge0}F_{n+1}x^{n+1} +x^2\sum_{n\ge0}F_nx^n

です。F0=0,F1=1F_0=0,F_1=1を用いると

F(x)−x=xF(x)+x2F(x)F(x)-x=xF(x)+x^2F(x)

なので、(1−x−x2)F(x)=x(1-x-x^2)F(x)=xを得ます。形式的べき級数1−x−x21-x-x^2の定数項は1なので逆数が存在し、結論を得ます。▨

3 フィボナッチ数列の一般項

α=(1+5)/2\alpha=(1+\sqrt5)/2、β=(1−5)/2\beta=(1-\sqrt5)/2とします。このとき1−x−x2=(1−αx)(1−βx)1-x-x^2=(1-\alpha x)(1-\beta x)です。

定理 3.1 (Binet の公式). すべての非負整数nnについて、

Fn=αn−βn5F_n=\frac{\alpha^n-\beta^n}{\sqrt5}

が成り立ちます。

証明. 部分分数分解により

x(1−αx)(1−βx)=15(11−αx−11−βx)\frac{x}{(1-\alpha x)(1-\beta x)} =\frac1{\sqrt5}\left(\frac1{1-\alpha x}-\frac1{1-\beta x}\right)

です。形式的等比級数

11−cx=∑n≥0cnxn\frac1{1-cx}=\sum_{n\ge0}c^nx^n

を用いると、

F(x)=∑n≥0αn−βn5xn.F(x)=\sum_{n\ge0}\frac{\alpha^n-\beta^n}{\sqrt5}x^n.

同じ次数の係数を比較すると結論を得ます。▨

4 例題

レベル3 — 母関数の入口

母関数（数列 a_0, a_1, … を係数に並べた式Σ\Sigmaa_nxnx^n、確率変数 X に対しては G(s)==E[sXs^X]==Σ\SigmaP(X==k)skk)s^k）を用いて答えよ。G′(1)==E[X]、G″(1)==E[X(X−1)] を使ってよい。

解法の型選び方を因子に翻訳して掛け合わせ、xkx^kの係数を読む。独立な和の母関数は積。期待値は G′(1)、分散は G″(1) + G′(1) − G′(1)²

数列 a_n は a_0==0、a_1==1、および n≥\ge2 で a_n==a_(n−1) + 2a_(n−2) を満たす。母関数 A(x)=Σ= \Sigmaa_nxnx^nを求め、部分分数分解して一般項 a_n を求めよ。

例 4.1.

a0=0,a1=1,an=an−1+2an−2 (n≥2),A(x)=∑n≥0anxn= ?,an= ?a_0 = 0,\quad a_1 = 1,\quad a_n = a_{n-1} + 2a_{n-2} \ (n \ge 2),\qquad A(x) = \sum_{n \ge 0} a_n x^n = \ ?,\quad a_n = \ ?

答

A(x)=x1−x−2x2=x(1−2x)(1+x)an=2n−(−1)n3\begin{array}{ll} A(x) &= \dfrac{x}{1 - x - 2x^{2}} = \dfrac{x}{(1 - 2x)(1 + x)} \\[6pt] a_n &= \dfrac{2^{n} - (-1)^{n}}{3} \end{array}

注意 漸化式にxnx^nを掛けて n≥\ge2 で足し合わせると、A(x) − x==x·A(x) + 2x²·A(x)（a_0==0, a_1==1 を使った）。整理して A(x)·(1 − x − 2x²)==x、すなわち A(x)==x/(1 − x − 2x²)。 分母は (1 − 2x)(1 + x) と因数分解できる（展開すると 1 − x − 2x² に戻る）。これは 2 と −1 が特性方程式 t²==t + 2 の解であることに対応する。 部分分数分解すると x/((1 − 2x)(1 + x))==(1/3)·(1/(1 − 2x) − 1/(1 + x))。各項を等比級数 1/(1 − cx)=Σcnxn= \Sigma c^n x^nに展開してxnx^nの係数を読むと a_n==(2^n − (−1)^n)/3。 検算: 漸化式から a_2==1, a_3==3, a_4==5。一般項に n==4 を入れると (2^4 − (−1)^4)/3==5 で一致する。 フィボナッチ数列（a_n==a_(n−1) + a_(n−2)）も同じ手順で A(x)==x/(1 − x − x²) となり、部分分数分解からビネの公式が出る（この場合は特性根が黄金比とその共役で無理数）。

5 演習

問題 5.1.a0=1a_0=1、an+1=2ana_{n+1}=2a_nで定める数列の通常母関数A(x)=∑n≥0anxnA(x)=\sum_{n\ge0}a_nx^nを求めよ。

解答.

漸化式へxn+1x^{n+1}を掛けてn≥0n\ge0について足すと、

∑n≥0an+1xn+1=2x∑n≥0anxn\sum_{n\ge0}a_{n+1}x^{n+1}=2x\sum_{n\ge0}a_nx^n

である。左辺はA(x)A(x)から定数項a0=1a_0=1を除いたものなので、A(x)−1=2xA(x)A(x)-1=2xA(x)であり、(1−2x)A(x)=1(1-2x)A(x)=1を得る。形式的べき級数1−2x1-2xの定数項は1なので逆数が存在し、A(x)=1/(1−2x)A(x)=1/(1-2x)である。▨

問題 5.2.1/(1−x)21/(1-x)^2のxnx^nの係数がn+1n+1であることを、1/(1−x)1/(1-x)の形式的等比級数を二つ掛けて示せ。

解答.

定理 3.1の証明で用いた形式的等比級数でc=1c=1とすると、1/(1−x)=∑i≥0xi1/(1-x)=\sum_{i\ge0}x^iである。したがって、

1(1−x)2=(∑i≥0xi)(∑j≥0xj)\frac1{(1-x)^2}=\left(\sum_{i\ge0}x^i\right)\left(\sum_{j\ge0}x^j\right)

であり、右辺のxnx^nの係数は、i+j=ni+j=nを満たす非負整数の組(i,j)(i,j)の個数である。そのような組はi=0,1,…,ni=0,1,\ldots,nに対してj=n−ij=n-iと定まるn+1n+1個なので、xnx^nの係数はn+1n+1である。▨

問題 5.3.定理 2.1の証明で、初期条件F0=0F_0=0、F1=1F_1=1がどの項に現れたかを説明せよ。

解答.

証明の式の左辺は、F(x)F(x)から次数0と次数1の項を除いたものなので、

∑n≥0Fn+2xn+2=F(x)−F0−F1x\sum_{n\ge0}F_{n+2}x^{n+2}=F(x)-F_0-F_1x

である。右辺の第1項の和は、F(x)F(x)から次数0の項を除いたものなので、

x∑n≥0Fn+1xn+1=x(F(x)−F0)x\sum_{n\ge0}F_{n+1}x^{n+1}=x\bigl(F(x)-F_0\bigr)

である。右辺の第2項x2F(x)x^2F(x)には初期条件は現れない。したがって、初期条件は、添字をずらしたときに分離する次数の低い項F0F_0とF1xF_1xに現れる。F0=0F_0=0、F1=1F_1=1を代入すると、左辺はF(x)−xF(x)-x、右辺の第1項はxF(x)xF(x)になる。▨

問題 5.4.a0=2a_0=2、an+1=3ana_{n+1}=3a_nで定める数列の通常母関数A(x)=∑n≥0anxnA(x)=\sum_{n\ge0}a_nx^nを求め、係数から一般項を示せ。

解答.

漸化式へxn+1x^{n+1}を掛けてn≥0n\ge0について足すと、左辺はA(x)A(x)から定数項a0=2a_0=2を除いたもの、右辺は3xA(x)3xA(x)なので、A(x)−2=3xA(x)A(x)-2=3xA(x)である。1−3x1-3xの定数項は1なので逆数が存在し、A(x)=2/(1−3x)A(x)=2/(1-3x)である。形式的等比級数でc=3c=3とすると、

A(x)=2∑n≥03nxn=∑n≥02⋅3nxnA(x)=2\sum_{n\ge0}3^nx^n=\sum_{n\ge0}2\cdot3^nx^n

である。同じ次数の係数を比較すると、すべての非負整数nnについてan=2⋅3na_n=2\cdot3^nである。▨

レベル3 — 母関数の入口

母関数（数列 a_0, a_1, … を係数に並べた式Σ\Sigmaa_nxnx^n、確率変数 X に対しては G(s)==E[sXs^X]==Σ\SigmaP(X==k)skk)s^k）を用いて答えよ。G′(1)==E[X]、G″(1)==E[X(X−1)] を使ってよい。

解法の型選び方を因子に翻訳して掛け合わせ、xkx^kの係数を読む。独立な和の母関数は積。期待値は G′(1)、分散は G″(1) + G′(1) − G′(1)²

問題 5.5. サイコロを 2 個投げるとき、出た目の和が 5 になる確率を、母関数の係数として求めよ。

(s+s2+s3+s4+s5+s66)2 の s5 の係数= ?\left(\dfrac{s + s^2 + s^3 + s^4 + s^5 + s^6}{6}\right)^{2} \ \text{の} \ s^{5} \ \text{の係数} = \ ?
解答.

答436=19(目の和が 5 になる出方は 4 通り)\dfrac{4}{36} = \dfrac{1}{9} \qquad \left(\text{目の和が } 5 \text{ になる出方は } 4 \text{ 通り}\right)

注意 サイコロ1個の母関数は (s + s² + … +s6)/6s^{6})/6（目 j が確率 1/6 で出るのでsjs^jの係数が 1/6）。2 個は独立なので、和の母関数はその 2 乗。s5s^5の係数がちょうど P(和==5)。 分子の (s + … +s6)2s^{6})^2を展開したときのs5s^5の係数（＝目の和が 5 になる出方の数）は 4 で、全体は 6^2==36 通り。よって確率は 4/36==1/9。 数え上げが多項式の掛け算に化けるのが母関数の要点。「各サイコロの選択肢を因子にして掛け合わせ、sks^kの係数を読む」。▨

問題 5.6. X は二項分布 B(9, 1/3) に従う。確率母関数 G(s)==E[sXs^X] を求め、G′(1) と G″(1) から期待値 E[X] と分散 V[X] を求めよ。

X∼B(9, 13),G(s)=E[sX]= ?,E[X]= ?,V[X]= ?X \sim B\left(9,\ \dfrac{1}{3}\right),\qquad G(s) = E[s^X] = \ ?,\quad E[X] = \ ?,\quad V[X] = \ ?
解答.

答

G(s)=(23+13s)9E[X]=3V[X]=2\begin{array}{ll} G(s) &= \left(\dfrac{2}{3} + \dfrac{1}{3}s\right)^{9} \\ E[X] &= 3 \\ V[X] &= 2 \end{array}

注意 X==X_1 + … + X_9（各 X_i は独立で、確率 p==1/3 で 1、確率 q==2/3 で 0）と書ける。1個分の母関数は q + ps で、独立な和の母関数は積だから G(s)==(q + ps)^9==(2/3 + (1/3)s)^9。 G′(s)==9p(q + ps)^8 より E[X]==G′(1)==9p==3（q + p==1 に注意）。G″(s)==9·8·p²(q + ps)^7 より E[X(X−1)]==G″(1)==9·8·p²==8。 V[X]==G″(1) + G′(1) − G′(1)²==n(n−1)p² + np − n²p²==np(1 − p)==npq==2。▨

問題 5.7. 数列 a_n は a_0==0、a_1==1、および n≥\ge2 で a_n==a_(n−1) + 6a_(n−2) を満たす。母関数 A(x)=Σ= \Sigmaa_nxnx^nを求め、部分分数分解して一般項 a_n を求めよ。

a0=0,a1=1,an=an−1+6an−2 (n≥2),A(x)=∑n≥0anxn= ?,an= ?a_0 = 0,\quad a_1 = 1,\quad a_n = a_{n-1} + 6a_{n-2} \ (n \ge 2),\qquad A(x) = \sum_{n \ge 0} a_n x^n = \ ?,\quad a_n = \ ?
解答.

答

A(x)=x1−x−6x2=x(1−3x)(1+2x)an=3n−(−2)n5\begin{array}{ll} A(x) &= \dfrac{x}{1 - x - 6x^{2}} = \dfrac{x}{(1 - 3x)(1 + 2x)} \\[6pt] a_n &= \dfrac{3^{n} - (-2)^{n}}{5} \end{array}

注意 漸化式にxnx^nを掛けて n≥\ge2 で足し合わせると、A(x) − x==x·A(x) + 6x²·A(x)（a_0==0, a_1==1 を使った）。整理して A(x)·(1 − x − 6x²)==x、すなわち A(x)==x/(1 − x − 6x²)。 分母は (1 − 3x)(1 + 2x) と因数分解できる（展開すると 1 − x − 6x² に戻る）。これは 3 と −2 が特性方程式 t²==t + 6 の解であることに対応する。 部分分数分解すると x/((1 − 3x)(1 + 2x))==(1/5)·(1/(1 − 3x) − 1/(1 + 2x))。各項を等比級数 1/(1 − cx)=Σcnxn= \Sigma c^n x^nに展開してxnx^nの係数を読むと a_n==(3^n − (−2)^n)/5。 検算: 漸化式から a_2==1, a_3==7, a_4==13。一般項に n==4 を入れると (3^4 − (−2)^4)/5==13 で一致する。 フィボナッチ数列（a_n==a_(n−1) + a_(n−2)）も同じ手順で A(x)==x/(1 − x − x²) となり、部分分数分解からビネの公式が出る（この場合は特性根が黄金比とその共役で無理数）。▨

問題 5.8. 1 円、2 円、5 円の3種類の硬貨がそれぞれ十分たくさんある。合計 6 円を作る方法は何通りあるか（同じ額面の硬貨は区別せず、枚数の組で数える）。母関数の係数として求めよ。

(1+x+x2+⋯ )(1+x2+x4+⋯ )(1+x5+x10+⋯ )=1(1−x)(1−x2)(1−x5) の x6 の係数= ?(1 + x + x^2 + \cdots)(1 + x^{2} + x^{4} + \cdots)(1 + x^{5} + x^{10} + \cdots) = \dfrac{1}{(1 - x)(1 - x^{2})(1 - x^{5})} \ \text{の} \ x^{6} \ \text{の係数} = \ ?
解答.

答55通り

注意 1 円硬貨を何枚使うかは 1 + x +x2x^2+ …==1/(1 − x)、同様に 2 円は 1/(1 −x2)x^2)、5 円は 1/(1 −x5)x^5)という因子で表せる（x の指数が金額、係数が場合の数）。 3種類は独立に選べるので、母関数はこれらの積 1/((1 − x)(1 −x2)(1x^2)(1−x5))x^5))。合計 6 円を作る方法の数は、この展開におけるx6x^6の係数。 硬貨を1種類ずつ順に取り込む畳み込み（金額 v について「1 円まで使ったときの通り数」→\to「2 円まで」→\to「5 円まで」と更新する）で係数を計算すると 5 通り。 「各要素の選び方を因子に翻訳し、掛け合わせてxkx^kの係数を読む」——選択肢が因子、答えが係数。▨

前提記事