Aritalab:Lecture/Basic/Generating Function

From Metabolomics.JP
< Aritalab:Lecture | Basic(Difference between revisions)
Jump to: navigation, search
m
Line 3: Line 3:
 
==母関数==
 
==母関数==
  
扱う対象とする無限列を、補助変数''z''を用いてべき級数(power series)として表現する方法を母関数という。
+
扱う対象とする無限列を、補助変数 ''z'' を用いてべき級数 (power series) として表現する方法を母関数 (generating function) といいます。
  
 
<math>
 
<math>
Line 9: Line 9:
 
</math>
 
</math>
  
例えば二項定理は、<math>(1+z)^r</math>が数列<math>\textstyle \binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots </math>の母関数表現と解釈できる。
+
例えば二項定理は、<math>(1+z)^r</math> が数列<math>\textstyle \binom{r}{0}, \binom{r}{1}, \binom{r}{2}, \ldots </math>の母関数表現と解釈できます。
  
 
<math>
 
<math>
Line 21: Line 21:
 
</math>
 
</math>
  
両者の<math>\Sigma</math>式において<math>z^n</math>の係数が等しいとおくことでヴァンデルモンドの畳み込み式(convolution)が得られる。
+
両者の &Sigma; 式において ''z<sup>n</sup>'' の係数が等しいとおくことでヴァンデルモンドの畳み込み式(convolution) が得られます。
  
 
<math>
 
<math>
Line 27: Line 27:
 
</math>
 
</math>
  
これを一般化すると以下のように書ける。
+
一般化すると以下のように書けます。
  
 
<math>
 
<math>

Revision as of 21:10, 25 May 2011

Wiki Top Up one level レポートの書き方 Arita Laboratory

Contents

母関数

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


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

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


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

この式を二つ掛け合わせると


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

両者の Σ 式において zn の係数が等しいとおくことでヴァンデルモンドの畳み込み式(convolution) が得られます。


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

一般化すると以下のように書けます。


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

Personal tools
Namespaces

Variants
Actions
Navigation
metabolites
Toolbox