母函数的性质及应用课件.pptx

1、母函数的性质及应用母函数的性质母函数的性质v定义 v母函数是用于对应一个无穷序列的幂级数，一般来说母函数有形式：02210)(nnnxgxgxggxG,210ggg母函数的性质母函数的性质v举一个例子：1,1,1,1,10321)(nnxxxxxGx11闭形式不考虑收敛问题！母函数的性质母函数的性质v基本操作v1放缩：2210)(xcgxcgcgxcG,210cgcgcg母函数的性质母函数的性质v2加减法：2221100)()()()()(xgfxgfgfxGxF,221100gfgfgf母函数的性质母函数的性质v3右移:22110)(kkkkxgxgxgxGx,0,02100gggk个母函数

2、的性质母函数的性质v4.求导：232132)(xgxggxG,3,2,321ggg母函数的性质母函数的性质v举一个求导的例子：xxxxxG111)(323224321)()1(1xxxxGx2)1(1x,5,4,3,2,1母函数的性质母函数的性质v5卷积规则：)()()()(22102210 xfxffxgxggxFxGxH022110fgfgfgfghnnnnn组合问题母函数的性质母函数的性质v简单的序列所对应的母函数mmmxxxxxxG)1(1111)1(1)(2 个nxxxm2111mnmnCg不定方程非负整数解的个数mx)1(1,112111mmmmmmCCC母函数的应用母函数的应用v

3、例1原创题 v例3Sweets母函数的应用母函数的应用v例1小明出门旅游，需要带一些食物，包括薯片，巧克力，矿泉水，汉堡，牛奶和糖果。经过估计，他觉得带n(n=10100)件食物比较合适，但他还有一些癖好：最多带1个汉堡巧克力的块数是5的倍数最多带4瓶矿泉水薯片的包数是一个偶数最多带3罐牛奶糖果的个数是4的倍数v问你小明有多少种方式来准备这次旅行所带的食物。母函数的应用母函数的应用v汉堡v巧克力v薯片v矿泉水v牛奶v糖果xxh1)(515105111)(xxxxxc2642111)(xxxxxpxxxxxxxw111)(5432xxxxxxm111)(43241284111)(xxxxxs母函

4、数的应用母函数的应用v运用卷积规则325224233445251)1(11111111111)1()()()()()()(xCxCxCxxxxxxxxxxsxmxwxpxcxh22nC母函数的性质母函数的性质v指数型母函数ng!ngn复杂简单！0!)(nnnnxgxG,210ggg母函数的性质母函数的性质v最基本的指数型母函数,1,1,1,1!4!3!2!11)(432xxxxxGxeTaylor公式 名称来源母函数的性质母函数的性质v乘积 2210!2!1)(xgxggxG2210!2!1)(xfxffxF000022102210)(!)!)!(!(!)!2!1)(!2!1()()()(nk

5、knknknnkknknCfgnxnknfkgnxxfxffxgxggxFxGxH排列问题！母函数的应用母函数的应用v例2Chocolatev例4证明题母函数的性质母函数的性质v母函数型Plya定理v（Plya定理）设G是n个对象的一个置换群，用m种颜色涂染这n个对象，则不同染色方案数为 1)()()(21gacacacmmmGl不够具体！母函数的性质母函数的性质v把m种颜色具体表示出来！giacnmnnacmacminiibbbbbbbbbGP1)(21)(22221)(21)()()121（母函数型Plya定理 母函数的性质母函数的性质v一个具体的例子：有4颗珠子绕成一圈，用两种颜色染色，旋转后重叠的方案算一种。)(),)(),(),)()()(3214423114324321vvvvvvvvvvvvvvvv置换群G：Plya定理 6)2222(4124l母函数的性质母函数的性质v母函数型Plya定理得具体的方案 432234442224442)()()()(41wbwwbwbbwbwbwbwbP2黑2白的有两种，4黑，4白，3黑1白，3白1黑的都只有1种 母函数的应用母函数的应用v例5 IOI2003国家集训队难题讨论活动0015 Polygon总结总结离散数学连续数学母函数v解决问题v优化算法v证明命题