生成函数幻灯片.ppt

《生成函数幻灯片.ppt》由会员分享，可在线阅读，更多相关《生成函数幻灯片.ppt（88页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、生成函数第1页，共88页，编辑于2022年，星期一5.1 引论第2页，共88页，编辑于2022年，星期一第3页，共88页，编辑于2022年，星期一第4页，共88页，编辑于2022年，星期一第5页，共88页，编辑于2022年，星期一第6页，共88页，编辑于2022年，星期一i=20j=0i=14j=1i=8j=2i=2j=3第7页，共88页，编辑于2022年，星期一5.2 形式幂级数第8页，共88页，编辑于2022年，星期一第9页，共88页，编辑于2022年，星期一第10页，共88页，编辑于2022年，星期一第11页，共88页，编辑于2022年，星期一5.3生成函数的性质第12页，共88页，编辑

2、于2022年，星期一第13页，共88页，编辑于2022年，星期一第14页，共88页，编辑于2022年，星期一第15页，共88页，编辑于2022年，星期一第16页，共88页，编辑于2022年，星期一积分满足结合律积分满足结合律第17页，共88页，编辑于2022年，星期一第18页，共88页，编辑于2022年，星期一第19页，共88页，编辑于2022年，星期一证明:(1)(1)(2)(2)(3)(3)牛顿二项式定理牛顿二项式定理k=0?第20页，共88页，编辑于2022年，星期一(4)(4)设设 则则 所以所以 (5)(5)第21页，共88页，编辑于2022年，星期一(6)(6)设设 则则 所以所以

3、 故故 第22页，共88页，编辑于2022年，星期一(7)(7)(8)(8)即二项式展开式即二项式展开式,既可以将其看作定义，也可以利用既可以将其看作定义，也可以利用x=0的指数函数的的指数函数的Taylor展开式证明此结果。展开式证明此结果。第23页，共88页，编辑于2022年，星期一(9)(9)前面学到的牛顿二项式定理知前面学到的牛顿二项式定理知,有有 故故 用用n+1替换替换n第24页，共88页，编辑于2022年，星期一第25页，共88页，编辑于2022年，星期一第26页，共88页，编辑于2022年，星期一k=n-1k=n-2第27页，共88页，编辑于2022年，星期一5.4 组合型分配

4、问题的生成函数第28页，共88页，编辑于2022年，星期一选取的元素个数为选取的元素个数为k第29页，共88页，编辑于2022年，星期一第30页，共88页，编辑于2022年，星期一第31页，共88页，编辑于2022年，星期一任意的整数集合任意的整数集合连续的整数区间连续的整数区间第32页，共88页，编辑于2022年，星期一5.4.2 组合型分配问题的生成函数组合型分配问题的生成函数任意的整数集合任意的整数集合第33页，共88页，编辑于2022年，星期一第34页，共88页，编辑于2022年，星期一n=10n=6n=0第35页，共88页，编辑于2022年，星期一二项式定理二项式定理第36页，共88

5、页，编辑于2022年，星期一第37页，共88页，编辑于2022年，星期一利用推论利用推论5.3.1第38页，共88页，编辑于2022年，星期一第39页，共88页，编辑于2022年，星期一第40页，共88页，编辑于2022年，星期一第41页，共88页，编辑于2022年，星期一第42页，共88页，编辑于2022年，星期一将将y2看作一看作一个变量个变量r=15第43页，共88页，编辑于2022年，星期一用生成函数的方法也可以求解不定方程的整数解的个数。例:求方程x1+x2+x3=1的整数解的个数，其中这个方程与原方程的解的个数相等。设解的个数为a13，则ar的生成函数是所以有第45页，共88页，编

6、辑于2022年，星期一5.5 排列数的指数型生成函数排列数的指数型生成函数5.5.1 排列数的指数型生成函数排列数的指数型生成函数第46页，共88页，编辑于2022年，星期一第47页，共88页，编辑于2022年，星期一第48页，共88页，编辑于2022年，星期一第49页，共88页，编辑于2022年，星期一第50页，共88页，编辑于2022年，星期一比较上式两边比较上式两边xn的系数得的系数得第51页，共88页，编辑于2022年，星期一第52页，共88页，编辑于2022年，星期一第53页，共88页，编辑于2022年，星期一第54页，共88页，编辑于2022年，星期一第55页，共88页，编辑于20

7、22年，星期一第56页，共88页，编辑于2022年，星期一第57页，共88页，编辑于2022年，星期一第58页，共88页，编辑于2022年，星期一比较两个定理比较两个定理第59页，共88页，编辑于2022年，星期一5.6 5.6 正整数的分拆正整数的分拆第60页，共88页，编辑于2022年，星期一第61页，共88页，编辑于2022年，星期一第62页，共88页，编辑于2022年，星期一5.6.1 5.6.1 有序分拆有序分拆第63页，共88页，编辑于2022年，星期一第64页，共88页，编辑于2022年，星期一第65页，共88页，编辑于2022年，星期一第66页，共88页，编辑于2022年，星期

8、一第67页，共88页，编辑于2022年，星期一第68页，共88页，编辑于2022年，星期一5.6.2 5.6.2 无序分拆无序分拆第69页，共88页，编辑于2022年，星期一第70页，共88页，编辑于2022年，星期一第71页，共88页，编辑于2022年，星期一第72页，共88页，编辑于2022年，星期一第73页，共88页，编辑于2022年，星期一5.6.3 分拆的分拆的Ferrers图图第74页，共88页，编辑于2022年，星期一第75页，共88页，编辑于2022年，星期一第76页，共88页，编辑于2022年，星期一第77页，共88页，编辑于2022年，星期一第78页，共88页，编辑于2022年，星期一第79页，共88页，编辑于2022年，星期一第80页，共88页，编辑于2022年，星期一第81页，共88页，编辑于2022年，星期一第82页，共88页，编辑于2022年，星期一第83页，共88页，编辑于2022年，星期一第84页，共88页，编辑于2022年，星期一5.6.4 分拆数的生成函数分拆数的生成函数第85页，共88页，编辑于2022年，星期一第86页，共88页，编辑于2022年，星期一第87页，共88页，编辑于2022年，星期一第88页，共88页，编辑于2022年，星期一