资源描述：
《第9-10讲 组合数学——分配问题》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第9-10讲分配问题整数的有序拆分(n个苹果，分给m个人)整数的无序拆分(n个苹果，分成m堆)集合的有序拆分(n种水果，分给m个人)集合的无序拆分(n种水果，分成m堆)整数的有序拆分将n个相同物体分配到m个不同位置上，称为整数的有序拆分，拆分数等于方程n=x1+x2+...+xm的解的个数分两种情况有空位无空位整数的有序拆分-无空位将n个相同物体分配到m个不同位置上，并且无空位，其拆分数记为Cm(n)。例14个相同物件全部分配到2个不同位置上（无空位），等价于求方程4=n1+n2的正整数解的个数。解：定理将一个正整数n分解成m(m≥1)个正
2、整数之和，即n=n1+n2+…+nm，如果考虑ni的次序,则其拆分数等于下列方程解的个数。整数的有序拆分-有空位拆分数用Bm(n)表示例2现有100台相同的微机，分配给10个系，每个系至少分6台，问有多少种分配方案？解：例34台机器分配到2个单位，列出其分配方案?解：整数的有序拆分例48台计算机分配给3个单位。第一个单位的分配量不超过3台，第二个单位分配量不超过4台，第三个单位分配量不超过5台，问有几种分配方案？解：解得14种分配方案。整数的有序拆分第10-11讲分配问题整数的有序拆分整数的无序拆分集合的有序拆分集合的无序拆分整数的无序拆分
3、将n个相同的物件分配到m个相同的位置上，称为整数的无序拆分。分两种情况无空位情况有空位情况整数的无序拆分-无空位将正整数n分成m个部分，n=n1+n2+…+nm(m≥1),ni≥1，且不考虑ni的次序，满足n1≥n2≥…≥nm,拆分数记为Pm(n)。定理：正整数n拆分成m个部分的方案数等于整数n的拆分中最大部分为m的方案数。记作：Pm(n)=Pm(n)若整数n拆分成1,2,…,m的和，并允许重复，其母函数为？整数的无序拆分-有空位当n≥m时，方案数=P1(n)+P2(n)+…+Pm(n)当n4、n)整数n拆分中，所有部分均为奇数，其母函数？整数n拆分中，所有部分不相等，其母函数？整数的无序拆分-有空位例5若用1克、2克、3克和4克砝码各一枚，问能称出哪几种重量？每种重量有几种可能方案？解：每种重量有10种可能方案。例6若有1克砝码3枚、2克砝码4枚、4克砝码2枚，问能称出哪几种重量？各有几种可能方案？解：能称出19种重量。整数的无序拆分-有空位定理：整数n拆分成不同整数和的拆分数 等于拆分成奇数之和的拆分数。例7求用1分、2分和3分面值的邮票贴出 不同面值的方案数（邮票允许重复）？解：例8求方程x1+2x2+4x3=17非负
5、整数解的个数？解：第10-11讲分配问题整数的有序拆分整数的无序拆分集合的有序拆分集合的无序拆分集合的有序划分（允许有空位）例9s={a,b,c}，分配到2个不同位置上，求其方案数？解：23=8例10用红、绿、蓝三种颜色给1×n棋盘着色，共有多少种着色方案？解： 共有3n种着色方案。集合的有序划分n个不同物件，全部分配到m个不同的位置上（允许有空位），其分配方案数为n个不同物件，全部分配到m个不同的位置上（不允许有空位），其分配方案数为第10-11讲分配问题整数的有序拆分整数的无序拆分集合的有序拆分集合的无序拆分集合的无序划分无空位划分
6、有空位划分特殊计数序列第一类斯特林数（Stirling数）组合意义：第一类Stirling数有正有負，其绝对值可以看做是将n个元素排成k个非空的圆排列的方案数。第二类斯特林数组合意义：是将n个不同元素的集合划分为k个非空集合的方案数。特殊计数序列第一类Stirling数定义[x]n=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)
7、-nS1(n,k)特殊计数序列第二类Stirling数定义称S2(n,k)为第二类Stirling数。特殊计数序列例11红、黄、蓝和白4种颜色的球，放到2个无区别的盒子里，不允许有空盒，求其方案。解：S2(4,2)1234567第1盒rybwryrbrw第2盒ybwrbwrywrybbwywyb特殊计数序列定理1：S2(n,k)，有下列性质S2(n,0)=0S2(n,1)=1S2(n,2)=2n-1-1S2(n,n-1)=C(n,2)S2(n,n)=1特殊计数序列定理2：S2(n,k)满足下面的递推关系S2(n,m)=mS2(n-1,m)+
8、S2(n-1,m-1)(n≥1,m≥1)证明设有n个有区别的球b1,b2,...,bn，从中任取一球设为b1。把n个球放到m个盒子无一空盒的方案的全体可分为两类：b1独占一盒，其
