《组合数学》课件第2章.pptx
《《组合数学》课件第2章.pptx》由会员分享,可在线阅读,更多相关《《组合数学》课件第2章.pptx(90页珍藏版)》请在文库网上搜索。
1、第二章 母函数及其应用第二章第二章 母函数及其应用母函数及其应用2.1 母函数母函数2.2 母函数的性质母函数的性质 2.3 指数型母函数指数型母函数 2.4 正整数的分拆正整数的分拆 第二章 母函数及其应用在第一章中,已经解决了部分排列组合方案的计数问题.但对于不尽相异元素的部分 排列和组合,用第一章的方法是比较麻烦的(参见表2.0.1).若改用母函数方法,问题将显 得容易多了.其次,在求解递推关系的解、整数分拆以及证明组合恒等式时,母函数方法是 一种非常重要的手段.第二章 母函数及其应用第二章 母函数及其应用2.1 母母 函函 数数定义定义 2.1.1 对于数列an,称无穷级数为该数列的普
2、通型母函 数,简称普母函数或母函数,同时称an为G(x)的生成数列.第二章 母函数及其应用【例【例 2.1.1】有限数列C(n,r),r=0,1,2,n 的普母函数是(1+x)n.【例【例 2.1.2】无限数列1,1,1,的普母函数是第二章 母函数及其应用说明说明(1)an 的非零值可以为有限个或无限个;(2)数列an与母函数一一对应,即给定数列便得知它的母函数;反之,求得母函数则数列也随之而定;(3)这里将母函数只看作一个形式函数,目的是利用其有关运算性质完成计数问题,故不考虑“收敛问题”,即始终认为它是收敛的,而且是可“逐项微分”和“逐项积分”的.表2.1.1是一些常用的母函数,它们的证明
3、只要利用解析函数展开成幂级数的方法即 可得到.第二章 母函数及其应用第二章 母函数及其应用定理定理 2.1.1 组合的母函数:设S=n1e1,n2e2,nm em,且n1+n2+nm=n,则S 的r 可重组合的母函数为其中,r 可重组合数为xr 之系数ar,r=0,1,2,n.第二章 母函数及其应用定理2.1.1的最大优点在于:(1)将无重组合与重复组合统一起来处理;(2)使处理可重组合的枚举问题变得非常简单.第二章 母函数及其应用第二章 母函数及其应用第二章 母函数及其应用推论推论6 设S=n1e1,n2e2,nm em,且n1+n2+nm=n,要求元素ei 至少出现ki 次,则S 的r 可
4、重组合的母函数为第二章 母函数及其应用【例【例 2.1.3】设有2个红球,1个黑球,1个白球,问:(1)共有多少种不同的选取方法.试加以枚举.(2)若每次从中任取3个,有多少种不同的取法.第二章 母函数及其应用第二章 母函数及其应用【例【例 2.1.4】有18张戏票分给甲、乙、丙、丁4个班(不考虑座位号),其中,甲、乙两 班最少1张,甲班最多5张,乙班最多6张;丙班最少2张,最多7张;丁班最少4张,最 多10张.可有多少种不同的分配方案?第二章 母函数及其应用第二章 母函数及其应用【例【例 2.1.5】从n 双互相不同的鞋中取出r 只(rn),要求其中没有任何两只是成对 的,共有多少种不同的取
5、法?第二章 母函数及其应用第二章 母函数及其应用这实际上是一种二次分配二次分配问题.即将r 个相同的球放入n 个不同的盒子,第i个盒子 最多放ti 个球,而该盒子又分为ni 个相异的格子,每个格子最多只能放一个球,故还需要 进行二次分配.如果第i个盒子中放进了ri 个球,那么,对该盒子而言,二次分配时的方 案数为 .例如,设甲、乙、丙3个班分别有30、28、22名学生,现把5本相同的书分给甲、乙、丙3个班,再发到个人手上,每人最多发一本.考虑将分给某班的某本书发给该班的同学 A 与将其发给同学B 被认为是不同的分法,而且甲、乙两班最少1本,甲班最多5本,乙 班最多6本,丙班最少2本,最多9本,
6、问共有多少种不同的分配方案.第二章 母函数及其应用第二章 母函数及其应用【例【例 2.1.6】甲、乙、丙3人把n(n3)本相同的书搬到办公室,要求甲和乙搬的本数一样多,问共有多少种分配的方法.解解 本问题即组合问题:从集合S=e1,e2,e3中可重复地选取n 个元 素,但要求e1 与e2 的个数一样多,求不同的选取方案数.设想当n=1时,其分法只有1种,即甲和乙都分0本,丙分1本.当n=2时,其分法有2种:甲和乙都分0本(丙分2本)或甲和乙都分1本(丙分0 本).当n=3时,也是2种分法.当n=4或5时,分法为3种:即甲和乙都分0本、1本或2本第二章 母函数及其应用一般情形,甲分k 本,乙也必
7、须分k 本,丙就只能分n-2k 本.考虑将分配过程分为3 步实现.第一步先选出2k 本书,第二步将选出的书分给甲、乙各一半,第三步将剩下的书 全分给丙.由于第二步属于二次分配,且只有一种分法,故可以将甲和乙视为一人,从而把 问题转换为:将n 本相同的书分给两个人,其中一人分得偶数本,求分配方法数.显然,本 问题的母函数为第二章 母函数及其应用第二章 母函数及其应用【例【例 2.1.7】证明组合等式证证 本例是母函数的另一种应用.意图说明普母函数除了能用于解决组合的求值问题 之外,还能用来证明很多组合等式.第二章 母函数及其应用第二章 母函数及其应用(3)因为第二章 母函数及其应用2.2 母函数
8、的性质母函数的性质由于母函数与它的生成数列之间是一一对应的,因此,若两个母函数之间存在某种关 系,则对应的生成数列之间也必然存在相应的关系.反之亦然.利用这类对应关系,常常能 帮助我们构造出某些指定数列的母函数的有限封闭形式.特别地,还能得到一些求和的新 方法.设数列ak、bk、ck的母函数分别为A(x)、B(x)、C(x),且都可逐项微分和积 分第二章 母函数及其应用第二章 母函数及其应用第二章 母函数及其应用第二章 母函数及其应用第二章 母函数及其应用第二章 母函数及其应用第二章 母函数及其应用第二章 母函数及其应用第二章 母函数及其应用2.3 指数型母函数指数型母函数第二章 母函数及其应
9、用但是,注意到n 集的r 无重排列数和r 无重组合数之间有如下关系:从而有第二章 母函数及其应用定义定义 2.3.1 对于数列ak=a0,a1,a2,把形式幂级数称为数列ak的指数型母函数指数型母函数,简称为指母函数指母函数,而数列ak则称为指母函数Ge(x)的生成序列生成序列.第二章 母函数及其应用说明说明(1)ak的非零值可以为有限个或无限个.(2)数列ak与母函数一一对应,即给定数列便得知它的指母函数;反之,求得指母 函数则数列也随之而定.(3)这里将指母函数只看做一个形式函数,目的是利用其有关运算性质完成计数问 题,故不考虑“收敛问题”,即始终认为它是收敛的,而且是可“逐项微分”和“逐
10、项积分”的.第二章 母函数及其应用(4)相应于同一数列ak,一般G(x)Ge(x).第二章 母函数及其应用第二章 母函数及其应用定理定理 2.3.1 设重集S=n1e1,n2e2,nm em,且n1+n2+nm=n,则 S 的r 可重排列的指母函数为其中,r 可重排列数为xr/r!之系数ar,r=0,1,2,n.第二章 母函数及其应用【例【例 2.3.1】盒中有3个红球,2个黄球,3个蓝球,从中取4个球,排成一列,问共有多少种不同排列方案.所以,从中取4个球的排列方案有70种.第二章 母函数及其应用类似于组合问题,令即对全部排列方案进行分类枚举.可以看出,取1个球的3种排列方案为红、黄、蓝各分
11、别 取1个.取2个球的9种排列方案为:红红、黄黄、蓝蓝、红黄、黄红、红蓝、蓝红、黄蓝、蓝黄.其它情形依此类推.第二章 母函数及其应用这里需要说明的是:(1)在例2.1.3中,利用普母函数可以将组合的每一种情况都枚举出来,但是对排列问 题,指母函数却做不到,只能对排列进行分类枚举.正如例2.3.1这样,项ryb 的系数6说 明红、蓝、黄球各取一个时,有6种排列方案,但每一种方案具体是什么,则无法表示出来 了.第二章 母函数及其应用第二章 母函数及其应用推论推论 1 若S=e1,e2,en,则r 无重排列的指母函数为第二章 母函数及其应用推论推论 2 若S=e1,e2,en,则r 无限可重排列的指
12、母函数为排列数为nr第二章 母函数及其应用推论推论 3 S=n1e1,n2e2,nm em,元素ei 至少取ki 个(ki0),则有推论推论 4 S=n1e1,n2e2,nm em,令r=n,即得全排列数第二章 母函数及其应用【例【例 2.3.2】五个数字1,1,2,2,3能组成多少个四位数?由a4=30知能组成30个四位数.同时还知道能组成3个一位数,8个两位数,18个三位 数等.第二章 母函数及其应用【例【例 2.3.3】求1,3,5,7,9五个数字组成的n 位数的个数(每个数字可重复出现),要求其中3,7出现的次数为偶数,1,5,9出现的次数不加限制.第二章 母函数及其应用【例【例 2.
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 组合数学 组合 数学 课件