1、1,第五章 生成函數(shù),5.1 生成函數(shù)的定義和性質(zhì) 5.2 組合數(shù)的生成函數(shù) 5.3 指數(shù)型生成函數(shù)與多重集的排列數(shù) 5.4 Catalan數(shù)列與Stirling數(shù)列的生成函數(shù) 5.5 分拆數(shù)的生成函數(shù),2,生成函數(shù),最早應用在1720年前后 組合計數(shù)方法， 將數(shù)列與形式冪級數(shù)聯(lián)系起來，成為連接離散數(shù)學與連續(xù)數(shù)學的橋梁。 美國著名計算數(shù)學家Wilf曾將生成函數(shù)形象地比喻成“一根晾衣繩”，其上掛滿了要展示的一列數(shù)。,多重集合的排列和組合 遞推關系的求解 正整數(shù)分拆 組合恒等式證明,4,生成函數(shù),生成函數(shù)方法的基本思想是把離散的數(shù)列同多項式或冪級數(shù)一一對應起來，從而把離散數(shù)列間的結(jié)合關系轉(zhuǎn)換為多項

2、式或冪級數(shù)之間的運算。,5.1 生成函數(shù)的定義與性質(zhì),定義 5.1.1 設有一個有限或無限數(shù)列,稱G(x)為序列,的生成函數(shù)，,做形式冪級數(shù),并記為,例5.1.1 求二項式系數(shù)的序列 的生成函數(shù)。,解：設要求的生成函數(shù)為G(x)，根據(jù)定義5.1.1， 由二項式定理，,例5.1.2 無限數(shù)列 1,1,., 的生成函數(shù)。 解：設要求的生成函數(shù)為G(x)，根據(jù)定義5.1.1， 由牛頓二項式定理的推論，,生成函數(shù)的定義,例5.1.3求數(shù)列 的生成函數(shù)，其中ak是多重集 的 k-組合數(shù),解：該數(shù)列記作ak ，它的生成函數(shù)是G(x)，則：,5.1.2 生成函數(shù)的性質(zhì),設數(shù)列 的生成函數(shù)為 ， 數(shù)列 的生成

3、函數(shù)為 ， 數(shù)列 的生成函數(shù)為 ，,10,生成函數(shù)的性質(zhì)（1）,性質(zhì)1 若 則,證明 根據(jù)已知條件，有,11,生成函數(shù)的性質(zhì)（2）,性質(zhì)2 若 則,證明 根據(jù)已知條件，有,12,生成函數(shù)的性質(zhì)（3）,性質(zhì)3 若 則,證明 等式 的兩端都乘以 ，得 以上各式兩邊分別相加，得,13,生成函數(shù)的性質(zhì)（4）,性質(zhì)4 若 則 其中 收斂,證明 因為 收斂，所以 是存在的，于是有 以上各式兩邊分別相加，得,14,生成函數(shù)的性質(zhì)（5）,性質(zhì)5 若 則,證明 由 的定義知,15,生成函數(shù)的性質(zhì)（6）,性質(zhì)6 若 則,證明 根據(jù)已知條件有,16,生成函數(shù)的性質(zhì)（7）,性質(zhì)7 若 則,證明 根據(jù)已知條件有,17,生成函數(shù)的性質(zhì)（8）,性質(zhì)8 若 則,證明 根據(jù)已知條件有,18,生成函數(shù)的性質(zhì)（9）,性質(zhì)9 若,證明：,一些數(shù)列的生成函數(shù),19,(1) (2) (3) (4) (5) (6) (7) (8),例5.2.1 求 的生成函數(shù),20,解 方法1 設 則： 所以 故,方法2,21,例5.2.2 已知 的生成函數(shù)為 求,22,解 方法1：用多項式的長除法得 則： 所以有,方法2 當k=0時，ak=2； 當k=1時，ak=22+3=7； 當k1時，ak=2k+1+32k-1-62k-2=2k+1；,23,，,，,例5.2.3 求前n個正整數(shù)的平方和,24,解 由前面列出的第（5）個數(shù)列的生成函