counting_chap8_1

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

Download Report