Aritalab:Lecture/Basic/Generating Function

Latest revision as of 09:34, 14 December 2012

[edit] 母関数

扱う対象とする無限列を、補助変数 z を用いてべき級数 (power series) として表現する方法を母関数 (generating function) といいます。

$G(z) = a_0 + a_1z + a_2z^2 + \cdots = \Sigma_{k=0}^{\infty}a_k z^k$

[edit] 母関数の例

ここでは以下の3つの公式を、母関数を用いて導きます。

$\begin{align} \sum^{\infty}_{n=0} (n+1)z^n &= 1/(1-z)^2 \\ \sum^{\infty}_{n=0} (kz)^n &= \frac{1}{1-kz} \\ \sum^{\infty}_{n=0} \binom{2n}{n}p^nq^n &= 1/\sqrt{1 - 4pq} \end{align}$

[edit] 自然数

a_n = n + 1 の母関数は

$1 + 2 z + 3 z^2 + \cdots = \textstyle\sum^{\infty}_{n=0} (n+1)z^n$

です。この右辺を閉じた式にするには

$z(1 + z + z^2 + \cdots) = \textstyle\sum^{\infty}_{n=0}z^{n+1} = \lim_{n \rightarrow \infty} \frac{z(1 - z^n)}{1-z} = z/(1-z)$

を使います。 $|z| < 1$ で収束すると仮定し、両辺を z について微分します。

$1 + 2 z + 3 z^2 + \cdots = 1/(1-z)^2$

少し拡張してみましょう。

$\textstyle\sum^{\infty}_{n=0}(n+k)z^n = \sum^{\infty}_{n=0}(n+1)z^n + (k-1) \sum^{\infty}_{n=0}z^n = \frac{1}{(1-z)^2} + \frac{k-1}{1-z} = \frac{ 1 + (k-1)(1-z)}{(1-z)^2}$

[edit] べき乗

a_n = 2ⁿ の母関数は

$1 + 2 z + 4 z^2 + \cdots = \textstyle\sum^{\infty}_{n=0} (2z)^n = \frac{1}{1-2z}$

です。ただし $|z| < 1/2$ と仮定します。一般化すれば a_n = kⁿ の母関数が 1/(1 − kz) になります。

[edit] 二項定理

二項定理は、 $(1+z)^r$ 　が数列 $\textstyle \binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots$ の母関数表現と解釈できます。すなわち

$\textstyle\sum_{k=0}^{\infty} \binom{r}{k} z^k = (1+z)^r$

が成立します。この式を二つ掛け合わせると

$(1+z)^r (1+z)^s = (1+z)^{r+s} = \textstyle\sum_{k=0}^{\infty} \binom{r+s}{k} z^k$

両者の Σ 式において zⁿ の係数が等しいとおけば

$\textstyle\sum_{k=0}^{n} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}$

が得られます。これをヴァンデルモンドの畳み込み式 (convolution) といいます。一般化すると以下のように書けます。

$\begin{align} F(z)G(z) &= (f_0 + f_1z + f_2z^2 + \cdots)(g_0 + g_1z + g_2z^2 + \cdots) \\ &= (f_0g_0) + (f_0g_1+ f_1g_0)z + (f_0g_2+f_1g_1+f_2g_0)z^2 + \cdots \\ &= \sum_n \Big( \sum_k f_k g_{n-k} \Big) z^n \end{align}$

二項定理の応用

数列 $\textstyle a_{2n} = \binom{2n}{n} p^n q^n , a_{2n+1} = 0 \ (n = 0, 1, 2, \cdots)$ の母関数が $\textstyle G(z) = 1/\sqrt{1 - 4pqz^2}$ になることを示しましょう。この式はランダムウォークの解析で出てきます。

まず数列の定義から

$\textstyle \sum^{\infty}_{m=0} a_m z^m = \sum^{\infty}_{n=0} a_{2n} z^{2n} = \sum^{\infty}_{n=0} \binom{2n}{n} (pqz^2)^n$

です。次に

$\begin{align} \binom{2n}{n} &= \frac{(2n)!}{n! n!} = \frac{2n(2n - 1)(2n - 2)(2n - 3) \cdots 4 \cdot 3 \cdot 2 \cdot 1}{n! n!} \\ &= \frac{\{2n \cdot 2(n-1) \cdot 2(n-2) \cdots 4 \cdot 2 \}\cdot \{ (2n-1)(2n-3)(2n-5) \cdots 3 \cdot 1\}}{n! n!} \\ &= \frac{2^n n! (2n-1)(2n-3)(2n-5) \cdots 5 \cdot 3 \cdot 1}{n! n!}\\ &= \frac{2^n (2n-1)(2n-3)(2n-5) \cdots 5 \cdot 3 \cdot 1}{n!}\\ &= \frac{2^{2n} \frac{(2n-1)}{2}\frac{(2n-3)}{2}\frac{(2n-5)}{2} \cdots \frac{5}{2} \cdot \frac{3}{2} \cdot \frac{1}{2}}{n!}\\ &= \frac{(-1)^n 4^n (- \frac{1}{2}) (- \frac{1}{2} -1) (- \frac{1}{2} -2) \cdots (- \frac{1}{2} - (n-2)) (- \frac{1}{2} - (n-1))}{n!} \end{align}$

と、二項定理 $\textstyle (1+z)^n = \sum_{k=0}^{\infty} \frac{n(n-1)\cdots (n-k+1)}{k!} z^k$ を用いて

$\begin{align} \sum^{\infty}_{n=0}\binom{2n}{n} (pqz^2)^n &= \sum^{\infty}_{n=0}\frac{(-1)^n 4^n (- \frac{1}{2}) (- \frac{1}{2} -1) (- \frac{1}{2} -2) \cdots (- \frac{1}{2} - (n-1))}{n!} (pqz^2)^n\\ &= \sum^{\infty}_{n=0}\frac{(- \frac{1}{2}) (- \frac{1}{2} -1) (- \frac{1}{2} -2) \cdots (- \frac{1}{2} - (n-1))}{n!} (-4pqz^2)^n\\ &= (1 - 4pqz^2)^{-1/2} \end{align}$

を示せました。この母関数で z = 1 とおくと $\textstyle \sum^{\infty}_{n=0} \binom{2n}{n}p^nq^n = (1 - 4pq)^{-1/2}$ になります。

@@ Line 1: / Line 1: @@
+{{Lecture/Header}}
 ==母関数==
-扱う対象とする無限列を補助変数''z''を用いてべき級数(power series)として表現するやり方を母関数という。
+扱う対象とする無限列を、補助変数 ''z'' を用いてべき級数 (power series) として表現する方法を母関数 (generating function) といいます。
 <math>
@@ Line 7: / Line 9: @@
 </math>
-例えば二項定理は、<math>(1+z)^r</math>が数列<math>\textstyle \binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots </math>の母関数だという意味になる。
+==母関数の例==
+ここでは以下の3つの公式を、母関数を用いて導きます。
+{| border="1"
+|
+<math>
+\begin{align}
+\sum^{\infty}_{n=0} (n+1)z^n &= 1/(1-z)^2 \\
+\sum^{\infty}_{n=0} (kz)^n &= \frac{1}{1-kz} \\
+\sum^{\infty}_{n=0} \binom{2n}{n}p^nq^n &= 1/\sqrt{1 - 4pq}
+\end{align}
+</math>
+|}
+===自然数===
+''a<sub>n</sub>'' = ''n'' + 1 の母関数は
 <math>
-(1+z)^r = \sum_{k=0}^{\infty} \binom{r}{k} z^k
++ 2 z + 3 z^2 + \cdots = \textstyle\sum^{\infty}_{n=0} (n+1)z^n
 </math>
-この式を二つ掛け合わせると
+です。この右辺を閉じた式にするには
 <math>
-(1+z)^r (1+z)^s = (1+z)^{r+s} = \sum_{k=0}^{\infty} \binom{r+s}{k} z^k
+z(1 + z + z^2 + \cdots) = \textstyle\sum^{\infty}_{n=0}z^{n+1} = \lim_{n \rightarrow \infty} \frac{z(1 - z^n)}{1-z} =  z/(1-z)
 </math>
-両者の<math>\Sigma</math>式において<math>z^n</math>の係数が等しいとおくことでヴァンデルモンドの畳み込み式(convolution)を得る。
+を使います。<math>|z| < 1</math> で収束すると仮定し、両辺を z について微分します。
 <math>
-\sum_{k=0}^{n} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}
++ 2 z + 3 z^2 + \cdots = 1/(1-z)^2
 </math>
-これを一般化すると以下のように書ける。
+少し拡張してみましょう。
+<math>\textstyle\sum^{\infty}_{n=0}(n+k)z^n = \sum^{\infty}_{n=0}(n+1)z^n + (k-1) \sum^{\infty}_{n=0}z^n =
+\frac{1}{(1-z)^2} + \frac{k-1}{1-z} = \frac{ 1 + (k-1)(1-z)}{(1-z)^2}</math>
+===べき乗===
+''a<sub>n</sub>'' = 2<sup>''n''</sup> の母関数は
+<math>
++ 2 z + 4 z^2 + \cdots = \textstyle\sum^{\infty}_{n=0} (2z)^n = \frac{1}{1-2z}
+</math>
+です。ただし <math>|z| < 1/2 </math> と仮定します。一般化すれば ''a<sub>n</sub>'' = k<sup>''n''</sup> の母関数が 1/(1 &minus; ''kz'') になります。
+===二項定理===
+二項定理は、<math>(1+z)^r</math>　が数列<math>\textstyle \binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots </math>の母関数表現と解釈できます。すなわち
+<math>
+\textstyle\sum_{k=0}^{\infty} \binom{r}{k} z^k = (1+z)^r
+</math>
+が成立します。この式を二つ掛け合わせると
+<math>
+(1+z)^r (1+z)^s = (1+z)^{r+s} = \textstyle\sum_{k=0}^{\infty} \binom{r+s}{k} z^k
+</math>
+両者の &Sigma; 式において ''z<sup>n</sup>'' の係数が等しいとおけば
+<math>
+\textstyle\sum_{k=0}^{n} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}
+</math>
+が得られます。これをヴァンデルモンドの畳み込み式 (convolution) といいます。
+一般化すると以下のように書けます。
 <math>
@@ Line 34: / Line 85: @@
 \end{align}
 </math>
+;二項定理の応用
+数列 <math>\textstyle a_{2n} = \binom{2n}{n} p^n q^n , a_{2n+1} = 0 \ (n = 0, 1, 2, \cdots)</math> の母関数が <math>\textstyle G(z) = 1/\sqrt{1 - 4pqz^2}</math> になることを示しましょう。この式はランダムウォークの解析で出てきます。
+まず数列の定義から
+<math>\textstyle
+\sum^{\infty}_{m=0} a_m z^m = \sum^{\infty}_{n=0} a_{2n} z^{2n} = \sum^{\infty}_{n=0} \binom{2n}{n} (pqz^2)^n
+</math>
+です。次に
+<math>
+\begin{align}
+\binom{2n}{n} &= \frac{(2n)!}{n! n!} = \frac{2n(2n - 1)(2n - 2)(2n - 3) \cdots 4 \cdot 3 \cdot 2 \cdot 1}{n! n!} \\
+&= \frac{\{2n \cdot 2(n-1) \cdot 2(n-2) \cdots 4 \cdot 2 \}\cdot \{ (2n-1)(2n-3)(2n-5) \cdots 3 \cdot 1\}}{n! n!} \\
+&= \frac{2^n n! (2n-1)(2n-3)(2n-5) \cdots 5 \cdot 3 \cdot 1}{n! n!}\\
+&= \frac{2^n (2n-1)(2n-3)(2n-5) \cdots 5 \cdot 3 \cdot 1}{n!}\\
+&= \frac{2^{2n} \frac{(2n-1)}{2}\frac{(2n-3)}{2}\frac{(2n-5)}{2} \cdots \frac{5}{2} \cdot \frac{3}{2} \cdot \frac{1}{2}}{n!}\\
+&= \frac{(-1)^n 4^n (- \frac{1}{2}) (- \frac{1}{2} -1) (- \frac{1}{2} -2) \cdots (- \frac{1}{2} - (n-2)) (- \frac{1}{2} - (n-1))}{n!}
+\end{align}
+</math>
+と、二項定理 <math>\textstyle (1+z)^n = \sum_{k=0}^{\infty} \frac{n(n-1)\cdots (n-k+1)}{k!} z^k</math> を用いて
+<math>
+\begin{align}
+\sum^{\infty}_{n=0}\binom{2n}{n} (pqz^2)^n &= \sum^{\infty}_{n=0}\frac{(-1)^n 4^n (- \frac{1}{2}) (- \frac{1}{2} -1) (- \frac{1}{2} -2) \cdots (- \frac{1}{2} - (n-1))}{n!} (pqz^2)^n\\
+&= \sum^{\infty}_{n=0}\frac{(- \frac{1}{2}) (- \frac{1}{2} -1) (- \frac{1}{2} -2) \cdots (- \frac{1}{2} - (n-1))}{n!} (-4pqz^2)^n\\
+&= (1 - 4pqz^2)^{-1/2}
+\end{align}
+</math>
+を示せました。この母関数で ''z'' = 1 とおくと <math>\textstyle \sum^{\infty}_{n=0} \binom{2n}{n}p^nq^n = (1 - 4pq)^{-1/2} </math> になります。

Aritalab:Lecture/Basic/Generating Function

Latest revision as of 09:34, 14 December 2012

Contents

[edit] 母関数

[edit] 母関数の例

[edit] 自然数

[edit] べき乗

[edit] 二項定理

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox