《组合数学生成函数的概念幻灯片.ppt》由会员分享，可在线阅读，更多相关《组合数学生成函数的概念幻灯片.ppt（19页珍藏版）》请在taowenge.com淘文阁网|工程机械CAD图纸|机械工程制图|CAD装配图下载|SolidWorks_CaTia_CAD_UG_PROE_设计图分享下载上搜索。
1、组合数学 生成函数的概念第1页，共19页，编辑于2022年，星期一第2章 生成函数n2.1 生成函数的概念n2.2 生成函数的运算n2.3 生成函数的幂级数展开式n2.4 指数生成函数n2.5 生成函数的应用补充第2页，共19页，编辑于2022年，星期一2.1 生成函数的概念n2.1.1 生成函数的定义n2.1.2 相同球分配到不同盒n2.1.2 重集的组合第3页，共19页，编辑于2022年，星期一2.1.1 生成函数的定义n定义2.1.1设x是一个抽象符号，an(n0,1,2,)为实数列，若函数F(x)可表示成 F(x)a0 x0a1x1a2x2 则称F(x)为数列an(n0,1,2,)的生
2、成函数生成函数(generating function)。并约定，若某个ai0(i0,1,2,)，则项aixi可以略去，且x0可简记为1。第4页，共19页，编辑于2022年，星期一2.1.1 生成函数的定义n数列 ,的生成函数 F(x)n无穷序列1,1,1,的生成函数为 F(x)x0 x1x2x3第5页，共19页，编辑于2022年，星期一 2.1.2 相同球分配到不同盒n例2.1.1 把9个相同球放入5个不同盒中，盒1中只能放奇数个，盒2中只能放偶数个，盒3中最少放2个且最多放5个，盒4与5的容量均不限，讨论其不同的方案数a9。第6页，共19页，编辑于2022年，星期一2.1.2 相同球分配到
3、不同盒n解解 用xk表示k个球，圆括号表示盒子，做nF(x)(x1x3x5)(x0 x2x4)(x2x3x4x5)(x0 x1x2x3)(x0 x1x2x3)盒1 盒2 盒3 盒4 盒5球的个数(3)(0)(2)(2)(2)x3 x0 x2 x2 x2x9球的个数(3)(2)(3)(0)(1)x3 x2 x3 x0 x1x9题意分配方案 F(x)右边展开式中x9项(未合并同类)a9F(x)右边展开式中x9项的系数第7页，共19页，编辑于2022年，星期一2.1.2 重集的组合n例2.1.2 设重集 S2a1,1a2,a3,9a4 试讨论S的7组合的个数b7第8页，共19页，编辑于2022年，星
4、期一2.1.2 重集的组合n解解 用4个圆括号分别表示a1,a2,a3,a4，做 F(x)(x0 x1x2)(x0 x1)(x0 x1x2)(x0 x1x2x9)2a1,2a3,3a4 x2 x0 x2 x3x71a1,1a2,4a3,1a4 x1 x1 x4 x1x77a4 x0 x0 x0 x7x7题意分配方案 F(x)右边展开式中x7项(未合并同类)b7F(x)右边展开式中x7项的系数第9页，共19页，编辑于2022年，星期一2.1.2 重集的组合n(1)求a1,a2,an的r组合数 F(x)(x0 x1)n(1x)n xr项的系数n(2)求a1,a2,an的r组合数 F(x)(x0 x1x2x3)n xr项的系数n(3)求t1a1,t2a2,tnan的r组合数 F(x)(x0 x1x2 )(x0 x1x2 )(x0 x1x2 )xr项的系数第10页，共19页，编辑于2022年，星期一第11页，共19页，编辑于2022年，星期一第12页，共19页，编辑于2022年，星期一第13页，共19页，编辑于2022年，星期一第14页，共19页，编辑于2022年，星期一第15页，共19页，编辑于2022年，星期一第16页，共19页，编辑于2022年，星期一第17页，共19页，编辑于2022年，星期一第18页，共19页，编辑于2022年，星期一第19页，共19页，编辑于2022年，星期一