Aritalab:Lecture/Basic/Generating Function

Revision as of 15:47, 7 July 2010

母関数

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

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

両者の $\Sigma$ 式において $z^n$ の係数が等しいとおくことでヴァンデルモンドの畳み込み式(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}$

Revision as of 15:21, 5 June 2010 (view source) Adm (Talk \| contribs) m ← Older edit		Revision as of 15:47, 7 July 2010 (view source) Adm (Talk \| contribs) Newer edit →
Line 1:		Line 1:
		+	{{Lecture/Header}}
		+
	==母関数==		==母関数==

Aritalab:Lecture/Basic/Generating Function

Revision as of 15:47, 7 July 2010

Contents

母関数

Personal tools

Namespaces

Variants

Views

Actions

Search

Navigation

metabolites

Toolbox