Aritalab:Lecture/Basic/Generating Function

Revision as of 22:00, 25 May 2011

母関数

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

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

母関数の例

自然数

a_n = n + 1 の母関数は

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

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

$z(1 + z + z^2 + \cdots) = \Sigma^{\infty}_{n=0}z^{n+1} = z/(1-z)$

が $|s| < 1$ で収束するので、両辺を微分して

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

が得られます。

べき乗

a_n = 2ⁿの母関数は

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

です。ただし $|z| < 1/2$ と仮定します。

二項定理

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

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

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

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

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

$\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}$

@@ Line 9: / Line 9: @@
 </math>
-例えば二項定理は、<math>(1+z)^r</math>　が数列<math>\textstyle \binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots </math>の母関数表現と解釈できます。
+==母関数の例==
+===自然数===
+''a<sub>n</sub>'' = ''n'' + 1 の母関数は
+<math>
++ 2 z + 3 z^2 + \cdots = \Sigma^{\infty}_{n=0} (n+1)z^n
+</math>
+です。この右辺を閉じた式にするには
+<math>
+z(1 + z + z^2 + \cdots) = \Sigma^{\infty}_{n=0}z^{n+1} = z/(1-z)
+</math>
+が <math>|s| < 1</math> で収束するので、両辺を微分して
+<math>
++ 2 z + 3 z^2 + \cdots = 1/(1-z)^2
+</math>
+が得られます。
+===べき乗===
+''a<sub>n</sub>'' = 2<sup>''n''</sup>の母関数は
+<math>
++ 2 z + 4 z^2 + \cdots = \Sigma^{\infty}_{n=0} (2z)^n = \frac{1}{1-2z}
+</math>
+です。ただし <math>|z| < 1/2 </math> と仮定します。
+===二項定理===
+二項定理は、<math>(1+z)^r</math>　が数列<math>\textstyle \binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots </math>の母関数表現と解釈できます。すなわち
 <math>
-(1+z)^r = \sum_{k=0}^{\infty} \binom{r}{k} z^k
+\sum_{k=0}^{\infty} \binom{r}{k} z^k = (1+z)^r
 </math>
-この式を二つ掛け合わせると
+が成立します。この式を二つ掛け合わせると
 <math>
@@ Line 21: / Line 55: @@
 </math>
-両者の &Sigma; 式において ''z<sup>n</sup>'' の係数が等しいとおくことでヴァンデルモンドの畳み込み式(convolution) が得られます。
+両者の &Sigma; 式において ''z<sup>n</sup>'' の係数が等しいとおけば
 <math>
@@ Line 27: / Line 61: @@
 </math>
+が得られます。これをヴァンデルモンドの畳み込み式 (convolution) といいます。
 一般化すると以下のように書けます。

Aritalab:Lecture/Basic/Generating Function

Revision as of 22:00, 25 May 2011

Contents

母関数

母関数の例

自然数

べき乗

二項定理

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox