Download presentation
Presentation is loading. Please wait.
1
Generating Functions （前半） B4 堺谷光
2
生成関数（type1） であるとき、 を、Aに関する生成関数と呼ぶ。 例えば、 のとき、
3
AとBがそれぞれ（0,0）,（5,7）からランダムに歩くとき、２つが出会う確率は？
Ex.8.1 AとBがそれぞれ（0,0）,（5,7）からランダムに歩くとき、２つが出会う確率は？ B Aは右か上 Bは左か下にランダムに動く A
4
AとBがそれぞれ（0,0）,（5,7）からランダムに歩くとき、２つが出会う確率は？
Ex.8.1 AとBがそれぞれ（0,0）,（5,7）からランダムに歩くとき、２つが出会う確率は？ B 出会うのは (0,6),(1,5),(2,4), (3,3),(4,2),(5,1) のどれか。 通り A
5
AとBがそれぞれ（0,0）,（5,7）からランダムに歩くとき、２つが出会う確率は？
Ex.8.1 AとBがそれぞれ（0,0）,（5,7）からランダムに歩くとき、２つが出会う確率は？ B A、Bともに全体で 通り 求める確率は、 生成関数は？ A
6
Ex.8.1 盤面が大きくなると、 の計算が大変 →生成関数を使って計算しよう
7
Ex.8.1 P(x) が多項式のとき、P(x) の の係数を とあらわす。 とすると、
8
Ex.8.1 、 とする。
9
Ex.8.1 以上より、 n=6のとき、
10
Ex.8.1 B A
11
Ex.8.1 以上より、 ちなみに、上の式はEx.3.10にでてきた からも導き出せる。
12
生成関数に関する性質 とする。 とすると、 とすると、 特に のとき、
13
生成関数に関する性質 とする。
14
命題8.1 とするとき、
15
Ex.8.2 のとき、 および を求めよ。 とすると、 で、 のとき、 よって
16
Ex.8.2 のとき、 および を求めよ。 なので、 命題8.1から、 これらはマクローリン展開と同じ。 （ｘの範囲に注意する必要あり）
17
Ex.8.3 フィボナッチ数列の陽関数表示を求めよ
18
Ex.8.3 フィボナッチ数列の陽関数表示を求めよ とすると、
19
Ex.8.3 フィボナッチ数列の陽関数表示を求めよ とすると、 同様に、
20
Ex.8.3 フィボナッチ数列の陽関数表示を求めよ なので、
21
Ex.8.3 フィボナッチ数列の陽関数表示を求めよ
22
Ex.8.4 次の条件を満たす1~nの並べ方の総数は？ n個のうち3つの数字を選び、左からa,b,cとする。
どうa,b,cを選んでも、b>a>c となっていない。 n=5のとき、 １ ３ ２ ５ ４ ４ １ ２ ５ ３
23
Ex.8.4 次の条件を満たす1~nの並べ方の総数は？ n個のうち3つの数字を選び、左からa,b,cとする。
どうa,b,cを選んでも、b>a>c となっていない。 条件を満たす並べ方の総数を nがk+1番目にあるとする。 あるi,ｊについて、 とすると、 条件に反する 任意のi,ｊについて
24
Ex.8.4 次の条件を満たす1~nの並べ方の総数は？ n個のうち3つの数字を選び、左からa,b,cとする。
どうa,b,cを選んでも、b>a>c となっていない。 の並べ方は 通り の並べ方は 通り
25
Ex.8.4 とする。 命題8.1より、 n≧1では上の２つが一致するので、
26
Ex.8.4 とし、これをマクローリン展開する
27
Ex.8.4 は負ではないので、
28
Ex.8.4 よって、 これより、
29
生成関数（type2） であるとき、 を、Aに関する生成関数(type2)と呼ぶ。
30
命題8.2 とするとき、
Similar presentations
