《第9-10讲 组合数学——分配问题》由会员分享，可在线阅读，更多相关《第9-10讲 组合数学——分配问题（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讲 分配问题,整数的有序拆分 整数的无序拆分 集合
5、的有序拆分 集合的无序拆分,集合的有序划分（允许有空位）,例9 s = a,b,c，分配到2个不同位置上，求其方案数？ 解：23=8 例10 用红、绿、蓝三种颜色给1n棋盘着色，共有多少种着色方案？ 解： 共有3n种着色方案。,集合的有序划分,n个不同物件，全部分配到m个不同的位置上（允许有空位），其分配方案数为 n个不同物件，全部分配到m个不同的位置上（不允许有空位），其分配方案数为,第10-11讲 分配问题,整数的有序拆分 整数的无序拆分 集合的有序拆分 集合的无序拆分,集合的无序划分,无空位划分 有空位划分,特殊计数序列,第一类斯特林数（Stirling数） 组合意义：第一类Stirli
6、ng数有正有負，其绝对值可以看做是将n个元素排成k个非空的圆排列的方案数。 第二类斯特林数 组合意义：是将n个不同元素的集合划分为k个非空集合的方案数。,特殊计数序列,第一类Stirling数定义 xn=x(x-1) (x-2) (x-n+1) =S1(n,0)+ S1(n,1)x+ S1(n,2)x2+.+ S1(n,n) xn 称S1(n,0), S1(n,1), S1(n,2),., S1(n,n)为第一类Stirling数 S1(n+1, k)=S1(n,k-1)-nS1(n,k),特殊计数序列,第二类Stirling数定义 称S2(n,k)为第二类Stirling数。,特殊计数序列,
7、例11 红、黄、蓝和白4种颜色的球，放到2个无区别的盒子里，不允许有空盒，求其方案。 解： S2(4,2),特殊计数序列,定理1：S2(n,k)，有下列性质 S2(n,0)=0 S2(n,1)=1 S2(n,2)=2n-1-1 S2(n,n-1)=C(n,2) S2(n,n)=1,特殊计数序列,定理2：S2(n,k)满足下面的递推关系 S2(n,m)=mS2(n-1,m)+S2(n-1,m-1)(n1, m1) 证明 设有n个有区别的球b1,b2,.,bn，从中任取一球设为b1 。 把n个球放到m个盒子无一空盒的方案的全体可分为两类： b1独占一盒，其方案数显然为S2 (n-1,m-1) b1
8、不独占一盒，这相当于先将剩下的n-1个球放到m个盒子，不允许空盒，共有S2 (n-1,m)种不同方案，然后将b1 球放进其中一盒，从乘法法则得不独占一盒的方案数应为mS2 (n-1,m)。 根据加法法则有 S2 (n,m)=S2 (n-1,m-1)+mS2 (n-1,m)。,特殊计数序列,根据定理2，有： 例12 把n个(n4)不同的球a1,a2,.,an放到3个相同的盒中（不允许空盒），并使a1所在的盒中至少有2个球，问有多少种方案？ 解：,特殊计数序列,Catalan数 在一个凸n边形中，用不在其内部相交的对角线把它拆分成若干个三角形，不同的拆分数为Cn,Catalan,特殊计数序列,特殊
9、计数序列,特殊计数序列,特殊计数序列,Catalan数 在一个凸n边形中，用不在其内部相交的对角线把它拆分成若干个三角形，不同的拆分数为Cn 序列C0,C1,.,Cn,.，满足以下递推关系 解得,Catalan,特殊计数序列,Catalan数 定理 n个+1和n个-1构成的2n项a1,a2,.,a2n，其部分和满足 a1+a2+.+ak0 (k = 1,2,., 2n) 的数列的个数等于第n个Catalan数,特殊计数序列,例13 有2n个人排成一行进入剧场。入场费50美分。2n个人中的n个人有50美分一个的分币，n个人有一美元的纸币。剧院售票处相当草率用一个空的现金收银机开始售票。有多少种列队方法使得只要有1美元的人买票，售票处就有50分币找零？ 解：,
