组合数学课件-第二章第五节指数型母函数.ppt
- 【下载声明】
1. 本站全部试题类文档,若标题没写含答案,则无答案;标题注明含答案的文档,主观题也可能无答案。请谨慎下单,一旦售出,不予退换。
2. 本站全部PPT文档均不含视频和音频,PPT中出现的音频或视频标识(或文字)仅表示流程,实际无音频或视频文件。请谨慎下单,一旦售出,不予退换。
3. 本页资料《组合数学课件-第二章第五节指数型母函数.ppt》由用户(晟晟文业)主动上传,其收益全归该用户。163文库仅提供信息存储空间,仅对该用户上传内容的表现方式做保护处理,对上传内容本身不做任何修改或编辑。 若此文所含内容侵犯了您的版权或隐私,请立即通知163文库(点击联系客服),我们立即给予删除!
4. 请根据预览情况,自愿下载本文。本站不保证下载资源的准确性、安全性和完整性, 同时也不承担用户因使用这些下载资源对自己和他人造成任何形式的伤害或损失。
5. 本站所有资源如无特殊说明,都需要本地电脑安装OFFICE2007及以上版本和PDF阅读器,压缩文件请下载最新的WinRAR软件解压。
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合 数学 课件 第二 五节 指数 函数
- 资源描述:
-
1、1第第2章章 递推关系与母函数递推关系与母函数 2.1 2.1 递推关系递推关系 2.2 2.2 母函数母函数(生成函数生成函数)2.3 Fibonacci 2.3 Fibonacci数列数列 2.4 2.4 优选法与优选法与FibonacciFibonacci序列的应用序列的应用 2.5 2.5 母函数的性质母函数的性质 2.6 2.6 线性常系数齐次递推关系线性常系数齐次递推关系 2.7 2.7 关于常系数非齐次递推关系关于常系数非齐次递推关系 2.8 2.8 整数的拆分整数的拆分 2.9 ferrers2.9 ferrers图像图像 2.10 2.10 拆分数估计拆分数估计 2.11 2
2、.11 指数型母函数指数型母函数 2.12 2.12 广义二项式定理广义二项式定理 2.13 2.13 应用举例应用举例 2.14 2.14 非线性递推关系举例非线性递推关系举例 2.15 2.15 递推关系解法的补充递推关系解法的补充22.11:指数型母函数:指数型母函数 2.11.1 2.11.1 问题的来源问题的来源 对对n n个互不相同的元素进行全排列,个互不相同的元素进行全排列,可得可得n!n!个不同的排列。个不同的排列。k k个不同的元素个不同的元素a a1 1,a,a2 2,a,ak k作允许重复作允许重复的排列的排列:如果如果a a1 1有有n n1 1个,个,a a2 2有有
3、n n2 2个,个,a ak k有有n nk k个,个,n n1 1+n+n2 2+n+nk k=n,=n,这样的这样的n n个元素进行全排列,不同的排个元素进行全排列,不同的排列数为:列数为:n!/(nn!/(n1 1!n!n2 2!n!nk k!)!)3 设有设有k种不同元素,若元素种不同元素,若元素a1最多最多取取n1个,元素个,元素a2 最多取最多取n2个,个,元,元素素ak最多取最多取nk 个,任取个,任取r个元素的排列个元素的排列数记为数记为pr,讨论序列讨论序列pr的情况的情况:2.11:指数型母函数:指数型母函数4 例例1 5个元素中个元素中a1重复了重复了3次,次,a2重复了
4、重复了2次,次,从中取从中取r个组合,其组合数为个组合,其组合数为cr,求取,求取1到到5的组合的组合序列的母函数。序列的母函数。G(x)=(1+x+x2+x3)(1+x+x2)=1+2x+3 x2+3 x3+2 x4+x5(1+x1+x12+x13)(1+x2+x22)展开式中展开式中3 3次方项如下:次方项如下:x1x22+x12x2+x13 x1x22对应的是取一个对应的是取一个x1,两个两个x2,若是作排若是作排列列,其不同排列数为:其不同排列数为:3!2!1!33!1!2!31!3!32.11:指数型母函数:指数型母函数5 为了便于计算,利用上述特点,形式地引进函数。为了便于计算,利
5、用上述特点,形式地引进函数。)!2!11)(!3!2!11()(G22231211exxxxxx!3!1!2!2!131221221xxxxx 展开后三次方项展开后三次方项3)!31!1!21!2!11(x)!3!3!1!2!3!2!1!3()!2!11)(!3!2!11()(G232exxxxxx!3)!3!3!1!2!3!2!1!3(3x2.11:指数型母函数:指数型母函数6 定义:对于序列定义:对于序列a0,a1,a2,a3,定义如下函数定义如下函数为序列为序列ai的指数型母函数。的指数型母函数。.!3!2!1)(G332210exaxaxaax2.11:指数型母函数:指数型母函数 例例
6、 5个元素中个元素中a1重复了重复了3次,次,a2重复了重复了2次,次,从中取从中取r个排列,其排列数为个排列,其排列数为cr,求取,求取1到到5的排列的排列序列的母函数。序列的母函数。)!2!11)(!3!2!11()(G232exxxxxx!3)!3!3!1!2!3!2!1!3(3x7 定理定理2.11.1:设有:设有k种不同元素,若元素种不同元素,若元素a1最多最多取取n1个,元素个,元素a2 最多取最多取n2个,个,元素,元素ak最多取最多取nk 个,任取个,任取r个元素的排列数记为个元素的排列数记为pr,则序列则序列pr的的指数型母函数为:指数型母函数为:)!.!21!1(.)!.!
7、21!1.()!.!21!1()(2221221knnnenxxxnxxxnxxxxGkpr的值为展开式中的值为展开式中xr/r!的系数。的系数。2.11:指数型母函数:指数型母函数8 证明:做完乘法,证明:做完乘法,xr项由如下形式的项组成:项由如下形式的项组成:kmmmmxmxmxk.2121m1+m2+mk=r2.11:指数型母函数:指数型母函数krmmmx.21!.!21rxmmmrrk项的系数为!rxrkmmmr.!21略略9 例例2 由由a,b,c,d这这4个符号取个符号取5个进行排列,要求个进行排列,要求a出现的次数不超过两次,但不能不出现,出现的次数不超过两次,但不能不出现,b
8、不超过不超过一次,一次,c出现的次数不超过出现的次数不超过3次,次,d出现的次数为偶出现的次数为偶数。求满足上上述条件的排列数。数。求满足上上述条件的排列数。解:构造母函数解:构造母函数Ge(x)。a )!2!1()(G2exxx b )!11(x c )!3!2!11(32xxxd )!4!21(42xx!1012600!97650!8140!71785!6645!5215!464!318!25!11098765432xxxxxxxxxx2.11:指数型母函数:指数型母函数10.!3!2!1132xxxex.!3!2!113322xkxkxkekx2.11:指数型母函数:指数型母函数1、2、
9、.!3!2!1132xxxex.!4!21242xxeexx.!3!123xxeexx11 例例3 由由A,G,C,T这这4个符号取个符号取n个进行排列,每个进行排列,每个字符都可以重复选取,求排列数。个字符都可以重复选取,求排列数。解:构造母函数解:构造母函数Ge(x)。)(xeG42)!.!2!11(nxxxnxe4.!34!24!1413322xxx排列数是排列数是4n。2.11:指数型母函数:指数型母函数12 例例4 求求1,3,5,7,9这这5个数字组成的个数字组成的n位数个数,位数个数,要求其中要求其中3出现的次数为偶数,其它数字出现的出现的次数为偶数,其它数字出现的次数无限制。(
10、用指数型母函数求解)次数无限制。(用指数型母函数求解)解:设满足条件的解:设满足条件的r r位数的数目为位数的数目为ar,则序则序列列a0,a1,a2,的母函数为:的母函数为:4242.)!21.)(!4!21()(xxxxxGe2.11:指数型母函数:指数型母函数134242.)!21.)(!4!21()(xxxxxGexxxeeeexG4)(21)()(35xxee 212.11:指数型母函数:指数型母函数)35(21nnna 因此14 例例4 求求1,3,5,7,9这这5个数字组成的个数字组成的n位数个数,位数个数,要求其中要求其中3出现的次数为偶数,其它数字出现的出现的次数为偶数,其它
展开阅读全文