Aritalab:Lecture/Basic/Generating Function - Revision history

Adm: /* 自然数 */

2012-12-14T00:34:59Z

‎自然数

Adm: /* 自然数 */

2012-12-14T00:30:24Z

‎自然数

Adm: /* 母関数の例 */

2011-10-13T03:08:33Z

‎母関数の例

Adm: /* 母関数の例 */

2011-06-09T01:13:40Z

‎母関数の例

Adm at 00:41, 9 June 2011

2011-06-09T00:41:09Z

Adm: /* 自然数 */

2011-06-09T00:33:05Z

‎自然数

Adm: /* 自然数 */

2011-05-26T03:12:38Z

‎自然数

Adm: /* 二項定理 */

2011-05-25T14:18:59Z

‎二項定理

Adm at 14:16, 25 May 2011

2011-05-25T14:16:38Z

Adm: /* べき乗 */

2011-05-25T13:20:35Z

‎べき乗

@@ Line 41: / Line 41: @@
 </math>
-少し拡張すると
+少し拡張してみましょう。
-<math>\textstyle\sum^{\infty}_{n=0}(n+k)z^n = \frac{1}{(1-z)^2} + \frac{k-1}{1-z} = \frac{ 1 + (k-1)(1-z)}{(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 =
 ===べき乗===

@@ Line 35: / Line 35: @@
 </math>
-を使います。<math>|z| < 1</math> で収束すると仮定すれば、両辺を微分して出来上がりです。
+を使います。<math>|z| < 1</math> で収束すると仮定し、両辺を z について微分します。
 <math>

@@ Line 26: / Line 26: @@
 <math>
-+ 2 z + 3 z^2 + \cdots = \sum^{\infty}_{n=0} (n+1)z^n
++ 2 z + 3 z^2 + \cdots = \textstyle\sum^{\infty}_{n=0} (n+1)z^n
 </math>
@@ Line 32: / Line 32: @@
 <math>
-z(1 + z + z^2 + \cdots) = \sum^{\infty}_{n=0}z^{n+1} = \lim_{n \rightarrow \infty} \frac{z(1 - z^n)}{1-z} =  z/(1-z)
+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>
@@ Line 40: / Line 40: @@
 + 2 z + 3 z^2 + \cdots = 1/(1-z)^2
 </math>
 ===べき乗===
@@ Line 45: / Line 49: @@
 <math>
-+ 2 z + 4 z^2 + \cdots = \sum^{\infty}_{n=0} (2z)^n = \frac{1}{1-2z}
++ 2 z + 4 z^2 + \cdots = \textstyle\sum^{\infty}_{n=0} (2z)^n = \frac{1}{1-2z}
 </math>
@@ Line 55: / Line 59: @@
 <math>
-\sum_{k=0}^{\infty} \binom{r}{k} z^k = (1+z)^r
+\textstyle\sum_{k=0}^{\infty} \binom{r}{k} z^k = (1+z)^r
 </math>
@@ Line 61: / Line 65: @@
 <math>
-(1+z)^r (1+z)^s = (1+z)^{r+s} = \sum_{k=0}^{\infty} \binom{r+s}{k} z^k
+(1+z)^r (1+z)^s = (1+z)^{r+s} = \textstyle\sum_{k=0}^{\infty} \binom{r+s}{k} z^k
 </math>
@@ Line 67: / Line 71: @@
 <math>
-\sum_{k=0}^{n} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}
+\textstyle\sum_{k=0}^{n} \binom{r}{k} \binom{s}{n-k} = \binom{r+s}{n}
 </math>

@@ Line 10: / Line 10: @@
 ==母関数の例==
-ここでは3つの公式を、母関数を用いて導きます。
+ここでは以下の3つの公式を、母関数を用いて導きます。
 {| border="1"
+|
@@ Line 16: / Line 16: @@
 \begin{align}
 \sum^{\infty}_{n=0} (n+1)z^n &= 1/(1-z)^2 \\
-\sum^{\infty}_{n=0} (2z)^n &= \frac{1}{1-2z} \\
+\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}

@@ Line 10: / Line 10: @@
 ==母関数の例==
 ===自然数===
@@ Line 15: / Line 26: @@
 <math>
-+ 2 z + 3 z^2 + \cdots = \Sigma^{\infty}_{n=0} (n+1)z^n
++ 2 z + 3 z^2 + \cdots = \sum^{\infty}_{n=0} (n+1)z^n
 </math>
@@ Line 21: / Line 32: @@
 <math>
-z(1 + z + z^2 + \cdots) = \Sigma^{\infty}_{n=0}z^{n+1} = \lim_{n \rightarrow \infty} \frac{z(1 - z^n)}{1-z} =  z/(1-z)
+z(1 + z + z^2 + \cdots) = \sum^{\infty}_{n=0}z^{n+1} = \lim_{n \rightarrow \infty} \frac{z(1 - z^n)}{1-z} =  z/(1-z)
 </math>
 を使います。<math>|z| < 1</math> で収束すると仮定すれば、両辺を微分して出来上がりです。
-;公式：　<math>
+<math>
 + 2 z + 3 z^2 + \cdots = 1/(1-z)^2
 </math>
@@ Line 34: / Line 45: @@
 <math>
-+ 2 z + 4 z^2 + \cdots = \Sigma^{\infty}_{n=0} (2z)^n = \frac{1}{1-2z}
++ 2 z + 4 z^2 + \cdots = \sum^{\infty}_{n=0} (2z)^n = \frac{1}{1-2z}
 </math>

@@ Line 21: / Line 21: @@
 <math>
-z(1 + z + z^2 + \cdots) = \Sigma^{\infty}_{n=0}z^{n+1} = z/(1-z)
+z(1 + z + z^2 + \cdots) = \Sigma^{\infty}_{n=0}z^{n+1} = \lim_{n \rightarrow \infty} \frac{z(1 - z^n)}{1-z} =  z/(1-z)
 </math>
-が <math>|s| < 1</math> で収束するので、両辺を微分して
+<math>|z| < 1</math> で収束すると仮定すれば、両辺を微分できて
 <math>

← Older revision		Revision as of 14:18, 25 May 2011
Line 104:		Line 104:
	</math>		</math>

−	を示せました。この母関数で ''z'' = 1 ~~とおけば~~ <math>\textstyle \sum^{\infty}_{n=0} \binom{2n}{n}p^nq^n = (1 - 4pq)^{-1/2} </math> ~~が示せました。~~	+	を示せました。この母関数で ''z'' = 1 とおくと <math>\textstyle \sum^{\infty}_{n=0} \binom{2n}{n}p^nq^n = (1 - 4pq)^{-1/2} </math> になります。

← Older revision		Revision as of 14:16, 25 May 2011
Line 71:		Line 71:
	\end{align}		\end{align}
	</math>		</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> が示せました。

@@ Line 33: / Line 33: @@
 ===べき乗===
-''a<sub>n</sub>'' = 2<sup>''n''</sup>の母関数は
+''a<sub>n</sub>'' = 2<sup>''n''</sup> の母関数は
 <math>
@@ Line 39: / Line 39: @@
 </math>
-です。ただし <math>|z| < 1/2 </math> と仮定します。
+です。ただし <math>|z| < 1/2 </math> と仮定します。一般化すれば ''a<sub>n</sub>'' = k<sup>''n''</sup> の母関数が 1/(1 &minus; ''kz'') になります。
 ===二項定理===