《第910讲组合数学——分配问题》由会员分享，可在线阅读，更多相关《第910讲组合数学——分配问题（32页珍藏版）》请在金锄头文库上搜索。
1、哈尔滨工程大学课件 沈晶 制作第第9-10讲讲 分配问题分配问题整数的有序拆分整数的有序拆分(n个苹果，分给个苹果，分给m个人个人)整数的无序拆分整数的无序拆分(n个苹果，分成个苹果，分成m堆堆)集合的有序拆分集合的有序拆分(n种水果，分给种水果，分给m个人个人)集合的无序拆分集合的无序拆分(n种水果，分成种水果，分成m堆堆)哈尔滨工程大学课件 沈晶 制作整数的有序拆分整数的有序拆分将将将将 n n 个相同物体分配到个相同物体分配到个相同物体分配到个相同物体分配到 m m 个不同位置上，称为整个不同位置上，称为整个不同位置上，称为整个不同位置上，称为整数的有序拆分，拆分数等于方程数的有序拆分，
2、拆分数等于方程数的有序拆分，拆分数等于方程数的有序拆分，拆分数等于方程n n = = x x1 1+ +x x2 2+.+.+x xmm的解的个数的解的个数的解的个数的解的个数分两种情况分两种情况分两种情况分两种情况有空位有空位有空位有空位无空位无空位无空位无空位哈尔滨工程大学课件 沈晶 制作整数的有序拆分整数的有序拆分-无空位无空位将将将将 n n 个相同物体分配到个相同物体分配到个相同物体分配到个相同物体分配到 m m 个不同位置上，并且无个不同位置上，并且无个不同位置上，并且无个不同位置上，并且无空位，其拆分数记为空位，其拆分数记为空位，其拆分数记为空位，其拆分数记为C Cmm( (n
3、n) )。例例例例1 1 4 4个相同物件全部分配到个相同物件全部分配到个相同物件全部分配到个相同物件全部分配到2 2个不同位置上（无个不同位置上（无个不同位置上（无个不同位置上（无空位），等价于求方程空位），等价于求方程空位），等价于求方程空位），等价于求方程4 = 4 = n n1 1+ +n n2 2的正整数解的个的正整数解的个的正整数解的个的正整数解的个数。数。数。数。解：解：解：解：哈尔滨工程大学课件 沈晶 制作定理定理将一个正整数将一个正整数将一个正整数将一个正整数 n n 分解成分解成分解成分解成 m m ( (mm1)1)个正整数之和，个正整数之和，个正整数之和，个正整数之和，
4、即即即即n n= =n n1 1+ +n n2 2+n nmm，如果考虑，如果考虑，如果考虑，如果考虑 n ni i 的次序的次序的次序的次序, , 则其拆分则其拆分则其拆分则其拆分数等于下列方程解的个数。数等于下列方程解的个数。数等于下列方程解的个数。数等于下列方程解的个数。 哈尔滨工程大学课件 沈晶 制作整数的有序拆分整数的有序拆分-有空位有空位拆分数用拆分数用拆分数用拆分数用B Bmm( (n n) )表示表示表示表示哈尔滨工程大学课件 沈晶 制作例例例例2 2 现有现有现有现有100100台相同的微机，分配给台相同的微机，分配给台相同的微机，分配给台相同的微机，分配给1010个系，每个
5、个系，每个个系，每个个系，每个系至少分系至少分系至少分系至少分6 6台，问有多少种分配方案？台，问有多少种分配方案？台，问有多少种分配方案？台，问有多少种分配方案？解：解：解：解：例例例例3 3 4 4台机器分配到台机器分配到台机器分配到台机器分配到2 2个单位，列出其分配方案个单位，列出其分配方案个单位，列出其分配方案个单位，列出其分配方案? ?解：解：解：解：整数的有序拆分整数的有序拆分哈尔滨工程大学课件 沈晶 制作例例例例4 4 8 8台计算机分配给台计算机分配给台计算机分配给台计算机分配给3 3个单位。第一个单位的分个单位。第一个单位的分个单位。第一个单位的分个单位。第一个单位的分配量
6、不超过配量不超过配量不超过配量不超过3 3台，第二个单位分配量不超过台，第二个单位分配量不超过台，第二个单位分配量不超过台，第二个单位分配量不超过4 4台，台，台，台，第三个单位分配量不超过第三个单位分配量不超过第三个单位分配量不超过第三个单位分配量不超过5 5台，问有几种分配方案台，问有几种分配方案台，问有几种分配方案台，问有几种分配方案？解：解：解：解：解得解得解得解得1414种分配方案。种分配方案。种分配方案。种分配方案。整数的有序拆分整数的有序拆分哈尔滨工程大学课件 沈晶 制作第第10-11讲讲 分配问题分配问题整数的有序拆分整数的有序拆分整数的无序拆分整数的无序拆分集合的有序拆分集合
7、的有序拆分集合的无序拆分集合的无序拆分哈尔滨工程大学课件 沈晶 制作整数的无序拆分整数的无序拆分将将将将n n个相同的物件分配到个相同的物件分配到个相同的物件分配到个相同的物件分配到mm个相同的位置上，称为个相同的位置上，称为个相同的位置上，称为个相同的位置上，称为整数的无序拆分。整数的无序拆分。整数的无序拆分。整数的无序拆分。分两种情况分两种情况分两种情况分两种情况无空位情况无空位情况无空位情况无空位情况有空位情况有空位情况有空位情况有空位情况哈尔滨工程大学课件 沈晶 制作整数的无序拆分整数的无序拆分-无空位无空位将正整数将正整数将正整数将正整数n n分成分成分成分成mm个部分，个部分，个部
8、分，个部分，n n= =n n1 1+ +n n2 2+n nmm( (mm 1), 1), n ni i 1 1，且不考虑，且不考虑，且不考虑，且不考虑n ni i的次序，满足的次序，满足的次序，满足的次序，满足n n1 1 n n2 2n nmm , , 拆分拆分拆分拆分数记为数记为数记为数记为P Pmm( (n n) )。定理：正整数定理：正整数定理：正整数定理：正整数n n拆分成拆分成拆分成拆分成mm个部分的方案数等于整数个部分的方案数等于整数个部分的方案数等于整数个部分的方案数等于整数n n的拆分中最大部分为的拆分中最大部分为的拆分中最大部分为的拆分中最大部分为mm的方案数。记作：的
9、方案数。记作：的方案数。记作：的方案数。记作：P Pmm( (n n)=)=P Pmm( (n n) )若整数若整数若整数若整数n n拆分成拆分成拆分成拆分成1,2,1,2,mm的和，并允许重复，其母的和，并允许重复，其母的和，并允许重复，其母的和，并允许重复，其母函数为？函数为？函数为？函数为？哈尔滨工程大学课件 沈晶 制作整数的无序拆分整数的无序拆分-有空位有空位当当当当n n mm时，方案数时，方案数时，方案数时，方案数= =P P1 1( (n n)+)+P P2 2( (n n)+)+P Pmm( (n n) )当当当当n n mm时，方案数时，方案数时，方案数时，方案数= =P P
10、1 1( (n n)+)+P P2 2( (n n)+)+P Pn n( (n n) )整数整数整数整数n n拆分中，所有部分均为奇数，其母函数？拆分中，所有部分均为奇数，其母函数？拆分中，所有部分均为奇数，其母函数？拆分中，所有部分均为奇数，其母函数？整数整数整数整数n n拆分中，所有部分不相等，其母函数？拆分中，所有部分不相等，其母函数？拆分中，所有部分不相等，其母函数？拆分中，所有部分不相等，其母函数？哈尔滨工程大学课件 沈晶 制作整数的无序拆分整数的无序拆分-有空位有空位例例例例5 5 若用若用若用若用1 1克、克、克、克、2 2克、克、克、克、3 3克和克和克和克和4 4克砝码各一枚
11、，问能克砝码各一枚，问能克砝码各一枚，问能克砝码各一枚，问能称出哪几种重量？每种重量有几种可能方案？称出哪几种重量？每种重量有几种可能方案？称出哪几种重量？每种重量有几种可能方案？称出哪几种重量？每种重量有几种可能方案？解：解：解：解：每种重量有每种重量有每种重量有每种重量有1010种可能方案。种可能方案。种可能方案。种可能方案。例例例例6 6 若有若有若有若有1 1克砝码克砝码克砝码克砝码3 3枚、枚、枚、枚、2 2克砝码克砝码克砝码克砝码4 4枚、枚、枚、枚、4 4克砝码克砝码克砝码克砝码2 2枚，枚，枚，枚，问能称出哪几种重量？各有几种可能方案？问能称出哪几种重量？各有几种可能方案？问能
12、称出哪几种重量？各有几种可能方案？问能称出哪几种重量？各有几种可能方案？解：解：解：解：能称出能称出能称出能称出1919种重量。种重量。种重量。种重量。哈尔滨工程大学课件 沈晶 制作整数的无序拆分整数的无序拆分-有空位有空位定理：整数定理：整数定理：整数定理：整数n n拆分成不同整数和的拆分数拆分成不同整数和的拆分数拆分成不同整数和的拆分数拆分成不同整数和的拆分数等于拆分成奇数之和的拆分数。等于拆分成奇数之和的拆分数。等于拆分成奇数之和的拆分数。等于拆分成奇数之和的拆分数。例例例例7 7 求用求用求用求用1 1分、分、分、分、2 2分和分和分和分和3 3分面值的邮票贴出分面值的邮票贴出分面值的
13、邮票贴出分面值的邮票贴出不同面值的方案数（邮票允许重复）？不同面值的方案数（邮票允许重复）？不同面值的方案数（邮票允许重复）？不同面值的方案数（邮票允许重复）？解：解：解：解：例例例例8 8 求方程求方程求方程求方程x x1 1+2+2x x2 2+4+4x x3 3=17=17非负整数解的个数？非负整数解的个数？非负整数解的个数？非负整数解的个数？解：解：解：解：哈尔滨工程大学课件 沈晶 制作第第10-11讲讲 分配问题分配问题整数的有序拆分整数的有序拆分整数的无序拆分整数的无序拆分集合的有序拆分集合的有序拆分集合的无序拆分集合的无序拆分哈尔滨工程大学课件 沈晶 制作集合的有序划分（允许有空
14、位）集合的有序划分（允许有空位）例例例例9 9 s s = = a a, ,b b, ,c c ，分配到，分配到，分配到，分配到2 2个不同位置上，求其方个不同位置上，求其方个不同位置上，求其方个不同位置上，求其方案数？案数？案数？案数？ 解：解：解：解：2 23=3=8 8 例例例例1010 用红、绿、蓝三种颜色给用红、绿、蓝三种颜色给用红、绿、蓝三种颜色给用红、绿、蓝三种颜色给11n n棋盘着色，共棋盘着色，共棋盘着色，共棋盘着色，共有多少种着色方案？有多少种着色方案？有多少种着色方案？有多少种着色方案？解：解：解：解：共有共有共有共有3 3n n种着色方案。种着色方案。种着色方案。种着色
15、方案。哈尔滨工程大学课件 沈晶 制作集合的有序划分集合的有序划分n n个不同物件，全部分配到个不同物件，全部分配到个不同物件，全部分配到个不同物件，全部分配到mm个不同的位置上（个不同的位置上（个不同的位置上（个不同的位置上（允允允允许有空位许有空位许有空位许有空位），其分配方案数为），其分配方案数为），其分配方案数为），其分配方案数为n n个不同物件，全部分配到个不同物件，全部分配到个不同物件，全部分配到个不同物件，全部分配到mm个不同的位置上（个不同的位置上（个不同的位置上（个不同的位置上（不不不不允许有空位允许有空位允许有空位允许有空位），其分配方案数为），其分配方案数为），其分配方案数
16、为），其分配方案数为哈尔滨工程大学课件 沈晶 制作第第10-11讲讲 分配问题分配问题整数的有序拆分整数的有序拆分整数的无序拆分整数的无序拆分集合的有序拆分集合的有序拆分集合的无序拆分集合的无序拆分哈尔滨工程大学课件 沈晶 制作集合的无序划分集合的无序划分无空位划分无空位划分无空位划分无空位划分有空位划分有空位划分有空位划分有空位划分哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列第一类斯特林数（第一类斯特林数（第一类斯特林数（第一类斯特林数（StirlingStirling数）数）数）数）组合意义：第一类组合意义：第一类组合意义：第一类组合意义：第一类StirlingStirling数
17、有正有負，其绝对值可以数有正有負，其绝对值可以数有正有負，其绝对值可以数有正有負，其绝对值可以看做是将看做是将看做是将看做是将n n个元素排成个元素排成个元素排成个元素排成k k个非空的圆排列的方案数。个非空的圆排列的方案数。个非空的圆排列的方案数。个非空的圆排列的方案数。第二类斯特林数第二类斯特林数第二类斯特林数第二类斯特林数组合意义：是将组合意义：是将组合意义：是将组合意义：是将n n个不同元素的集合划分为个不同元素的集合划分为个不同元素的集合划分为个不同元素的集合划分为k k个非空集个非空集个非空集个非空集合的方案数。合的方案数。合的方案数。合的方案数。哈尔滨工程大学课件 沈晶 制作特殊
18、计数序列特殊计数序列第一类第一类第一类第一类StirlingStirling数定义数定义数定义数定义 x x n n= =x x ( (x x-1) -1) ( (x x-2) -2) ( (x x- -n n+1)+1) = =S S1 1( (n n,0)+ ,0)+ S S1 1( (n n,1),1)x x+ + S S1 1( (n n,2),2)x x2 2+.+ +.+ S S1 1( (n n, ,n n) ) x xn n 称称称称S S1 1( (n n,0), ,0), S S1 1( (n n,1), ,1), S S1 1( (n n,2),., ,2),., S S
19、1 1( (n n, ,n n) )为为第一第一第一第一类类StirlingStirling数数数数S S1 1( (n+n+1, 1, k k)=)=S S1 1( (n n, ,k k-1)-1)-nSnS1 1( (n n, ,k k) ) 哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列第二类第二类第二类第二类StirlingStirling数定义数定义数定义数定义称称称称S S2 2( (n n, ,k k) )为第二类为第二类为第二类为第二类StirlingStirling数。数。数。数。哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列例例例例1111 红、黄、蓝和白红
20、、黄、蓝和白红、黄、蓝和白红、黄、蓝和白4 4种颜色的球，放到种颜色的球，放到种颜色的球，放到种颜色的球，放到2 2个无区个无区个无区个无区别的盒子里，不允许有空盒，求其方案。别的盒子里，不允许有空盒，求其方案。别的盒子里，不允许有空盒，求其方案。别的盒子里，不允许有空盒，求其方案。解：解：解：解： S S2 2(4,2)(4,2)1 12 23 34 45 56 67 7第第第第1 1盒盒盒盒r ry yb bw wryryrbrbrwrw第第第第2 2盒盒盒盒ybwybw rbw rbw ryw ryw ryb rybbwbwywywybyb哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计
21、数序列定理定理定理定理1 1：S S2 2( (n n, ,k k) )，有下列性质，有下列性质，有下列性质，有下列性质S S2 2( (n n,0)=0,0)=0S S2 2( (n n,1)=1,1)=1S S2 2( (n n,2)=2,2)=2n n-1-1-1-1S S2 2( (n n, ,n n-1)=-1)=C C(n,2)(n,2)S S2 2( (n n, ,n n)=1)=1哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列定理定理定理定理2 2：S S2 2( (n n, ,k k) )满足下面的递推关系满足下面的递推关系满足下面的递推关系满足下面的递推关系 S S
22、2 2( (n n, ,mm)=)=mSmS2 2( (n n-1,-1,mm)+)+S S2 2( (n n-1,-1,mm-1)(-1)(n n1, 1, mm11) )证明证明证明证明 设有设有设有设有n n个有区别的球个有区别的球个有区别的球个有区别的球b b1 1, ,b b2 2,.,.,b bn n，从中任取一球设为，从中任取一球设为，从中任取一球设为，从中任取一球设为b b1 1 。 把把把把n n个球放到个球放到个球放到个球放到mm个盒子无一空盒的方案的全体可分为两类：个盒子无一空盒的方案的全体可分为两类：个盒子无一空盒的方案的全体可分为两类：个盒子无一空盒的方案的全体可分为
23、两类：b b1 1独占一盒，其方案数显然为独占一盒，其方案数显然为独占一盒，其方案数显然为独占一盒，其方案数显然为S S2 2 ( (n n-1,-1,mm-1)-1)b b1 1不独占一盒，这相当于先将剩下的不独占一盒，这相当于先将剩下的不独占一盒，这相当于先将剩下的不独占一盒，这相当于先将剩下的n n-1-1个球放到个球放到个球放到个球放到mm个盒子，不允个盒子，不允个盒子，不允个盒子，不允许空盒，共有许空盒，共有许空盒，共有许空盒，共有S S2 2 ( (n n-1,-1,mm) )种不同方案，然后将种不同方案，然后将种不同方案，然后将种不同方案，然后将b b1 1 球放进其中一盒，球放
24、进其中一盒，球放进其中一盒，球放进其中一盒，从乘法法则得不独占一盒的方案数应为从乘法法则得不独占一盒的方案数应为从乘法法则得不独占一盒的方案数应为从乘法法则得不独占一盒的方案数应为mSmS2 2 ( (n n-1,-1,mm) )。根据加法法则有根据加法法则有根据加法法则有根据加法法则有 S S2 2 ( (n n, ,mm)=)=S S2 2 ( (n n-1,-1,mm-1)+-1)+mSmS2 2 ( (n n-1,-1,mm) )。 哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列根据定理根据定理根据定理根据定理2 2，有：，有：，有：，有：例例例例1212 把把把把n n个个个
25、个(n(n4)4)不同的球不同的球不同的球不同的球a a1 1, ,a a2 2,.,.,a an n放到放到放到放到3 3个相同个相同个相同个相同的盒中（不允许空盒），并使的盒中（不允许空盒），并使的盒中（不允许空盒），并使的盒中（不允许空盒），并使a a1 1所在的盒中至少所在的盒中至少所在的盒中至少所在的盒中至少有有有有2 2个球，问有多少种方案？个球，问有多少种方案？个球，问有多少种方案？个球，问有多少种方案？解：解：解：解：哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列CatalanCatalan数数数数在一个凸在一个凸在一个凸在一个凸n n边形中，用不在其内部相交的对角线把
26、它拆边形中，用不在其内部相交的对角线把它拆边形中，用不在其内部相交的对角线把它拆边形中，用不在其内部相交的对角线把它拆分成若干个三角形，不同的拆分数为分成若干个三角形，不同的拆分数为分成若干个三角形，不同的拆分数为分成若干个三角形，不同的拆分数为C Cn nCatalanCatalan哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列CatalanCatalan数数数数在一个凸在一个凸在一个凸在一个凸n n边形中，用不在其内部相交
27、的对角线把它拆边形中，用不在其内部相交的对角线把它拆边形中，用不在其内部相交的对角线把它拆边形中，用不在其内部相交的对角线把它拆分成若干个三角形，不同的拆分数为分成若干个三角形，不同的拆分数为分成若干个三角形，不同的拆分数为分成若干个三角形，不同的拆分数为C Cn n序列序列序列序列C C0 0, ,C C1 1,.,.,C Cn n,.,.，满足以下递推关系，满足以下递推关系，满足以下递推关系，满足以下递推关系解得解得解得解得CatalanCatalan哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列CatalanCatalan数数数数定理定理定理定理 n n个个个个+1+1和和和和n
28、 n个个个个-1-1构成的构成的构成的构成的2 2n n项项项项a a1 1, ,a a2 2,.,.,a a2 2n n，其部分和满，其部分和满，其部分和满，其部分和满足足足足 a a1 1+ +a a2 2+.+.+a ak k0 (0 (k k = 1,2,., 2= 1,2,., 2n n) ) 的数列的个数等于第的数列的个数等于第的数列的个数等于第的数列的个数等于第n n个个个个CatalanCatalan数数数数哈尔滨工程大学课件 沈晶 制作特殊计数序列特殊计数序列例例例例1313 有有有有2 2n n个人排成一行进入剧场。入场费个人排成一行进入剧场。入场费个人排成一行进入剧场。入
29、场费个人排成一行进入剧场。入场费5050美分。美分。美分。美分。2 2n n个人中的个人中的个人中的个人中的n n个人有个人有个人有个人有5050美分一个的分币，美分一个的分币，美分一个的分币，美分一个的分币，n n个人有个人有个人有个人有一美元的纸币。剧院售票处相当草率用一个空的一美元的纸币。剧院售票处相当草率用一个空的一美元的纸币。剧院售票处相当草率用一个空的一美元的纸币。剧院售票处相当草率用一个空的现金收银机开始售票。有多少种列队方法使得只现金收银机开始售票。有多少种列队方法使得只现金收银机开始售票。有多少种列队方法使得只现金收银机开始售票。有多少种列队方法使得只要有要有要有要有1 1美元的人买票，售票处就有美元的人买票，售票处就有美元的人买票，售票处就有美元的人买票，售票处就有5050分币找零？分币找零？分币找零？分币找零？解：解：解：解：
