第9-10讲组合数学——分配问题.ppt
《第9-10讲组合数学——分配问题.ppt》由会员分享,可在线阅读,更多相关《第9-10讲组合数学——分配问题.ppt(32页珍藏版)》请在三一文库上搜索。
1、第9-10讲 分配问题,整数的有序拆分(n个苹果,分给m个人) 整数的无序拆分(n个苹果,分成m堆) 集合的有序拆分(n种水果,分给m个人) 集合的无序拆分(n种水果,分成m堆),整数的有序拆分,将 n 个相同物体分配到 m 个不同位置上,称为整数的有序拆分,拆分数等于方程n = x1+x2+.+xm的解的个数 分两种情况 有空位 无空位,整数的有序拆分-无空位,将 n 个相同物体分配到 m 个不同位置上,并且无空位,其拆分数记为Cm(n)。 例1 4个相同物件全部分配到2个不同位置上(无空位),等价于求方程4 = n1+n2的正整数解的个数。 解:,定理,将一个正整数 n 分解成 m (m1
2、)个正整数之和,即n=n1+n2+nm,如果考虑 ni 的次序, 则其拆分数等于下列方程解的个数。,整数的有序拆分-有空位,拆分数用Bm(n)表示,例2 现有100台相同的微机,分配给10个系,每个系至少分6台,问有多少种分配方案? 解: 例3 4台机器分配到2个单位,列出其分配方案? 解:,整数的有序拆分,例4 8台计算机分配给3个单位。第一个单位的分配量不超过3台,第二个单位分配量不超过4台,第三个单位分配量不超过5台,问有几种分配方案? 解: 解得14种分配方案。,整数的有序拆分,第10-11讲 分配问题,整数的有序拆分 整数的无序拆分 集合的有序拆分 集合的无序拆分,整数的无序拆分,将
3、n个相同的物件分配到m个相同的位置上,称为整数的无序拆分。 分两种情况 无空位情况 有空位情况,整数的无序拆分-无空位,将正整数n分成m个部分,n=n1+n2+nm(m1), ni1,且不考虑ni的次序,满足n1n2nm , 拆分数记为Pm(n)。 定理:正整数n拆分成m个部分的方案数等于整数n的拆分中最大部分为m的方案数。记作:Pm(n)=Pm(n) 若整数n拆分成1,2,m的和,并允许重复,其母函数为?,整数的无序拆分-有空位,当nm时,方案数=P1(n)+P2(n)+Pm(n) 当n m时,方案数=P1(n)+P2(n)+Pn(n) 整数n拆分中,所有部分均为奇数,其母函数? 整数n拆分
4、中,所有部分不相等,其母函数?,整数的无序拆分-有空位,例5 若用1克、2克、3克和4克砝码各一枚,问能称出哪几种重量?每种重量有几种可能方案? 解: 每种重量有10种可能方案。 例6 若有1克砝码3枚、2克砝码4枚、4克砝码2枚,问能称出哪几种重量?各有几种可能方案? 解: 能称出19种重量。,整数的无序拆分-有空位,定理:整数n拆分成不同整数和的拆分数 等于拆分成奇数之和的拆分数。 例7 求用1分、2分和3分面值的邮票贴出 不同面值的方案数(邮票允许重复)? 解: 例8 求方程x1+2x2+4x3=17非负整数解的个数? 解:,第10-11讲 分配问题,整数的有序拆分 整数的无序拆分 集合
- 配套讲稿:
如PPT文件的首页显示word图标,表示该PPT已包含配套word讲稿。双击word图标可打开word文档。
- 特殊限制:
部分文档作品中含有的国旗、国徽等图片,仅作为作品整体效果示例展示,禁止商用。设计者仅对作品中独创性部分享有著作权。
- 关 键 词:
- 10 组合 数学 分配 问题
链接地址:https://www.31doc.com/p-3435916.html