组合数学课件--第一章：排列与组合

1、1 组合数学组合数学 课时：课时：36学时学时 成绩分配：平时成绩成绩分配：平时成绩30分，期末考分，期末考 试成绩试成绩70分。分。 平时成绩取得方式：安排平时成绩取得方式：安排5次课堂次课堂 测验，每次测验，每次6分。分。 课件邮箱课件邮箱: 密码密码:20070826 2 组合数学的应用范畴组合数学的应用范畴 从广义上讲组合数学就是离散数学从广义上讲组合数学就是离散数学 组合数学研究满足一定条件的组合模型的组合数学研究满足一定条件的组合模型的 情况情况: (1)存在性：存在性： (2)计数：计数： (3)有哪些？有哪些？ (4)哪些最优？哪些最优？ 组合数学与组合数学与算法、算法、 密码

2、学、编码理论、数密码学、编码理论、数 据压缩等计算机方向密据压缩等计算机方向密 不可分。不可分。 * 3 选用教材选用教材 组合数学组合数学 (第四版第四版) 卢开澄卢开澄 卢华明卢华明 著著 清华大学出版社清华大学出版社 4 组合数学的应用范畴组合数学的应用范畴 第一章第一章:排列与组合排列与组合 第二章第二章:递推关系与母函数递推关系与母函数 第三章第三章:容斥原理与鸽巢原理容斥原理与鸽巢原理 第四章第四章:Burnside引理与引理与Polya定理定理 第五章第五章:区组设计区组设计 第六章第六章:线性规划线性规划 第七章第七章:编码简介编码简介 第八章第八章:组合算法简介组合算法简介

3、5 参考教材参考教材 组合数学组合数学 Richard A. Brualdi 著著 冯舜玺等译冯舜玺等译 机械工业出版社机械工业出版社 6 参考教材参考教材 组合数学及其算法组合数学及其算法 杨振生杨振生 中国科学技术大学出版社中国科学技术大学出版社 7 第一章：排列与组合第一章：排列与组合 1.1 基本计数法则基本计数法则 1.2 一一对应一一对应: 1.3 排列与组合排列与组合 1.4 圆周排列圆周排列 1.5 排列的生成算法排列的生成算法 1.6 允许重复的组合与不相邻的组合允许重复的组合与不相邻的组合 1.7 组合意义的解释组合意义的解释 1.8 应用举例应用举例 1.9 *Stirl

4、ing公式公式 8 1.1基本计数法则基本计数法则 1、加法法则、加法法则: 如果具有性质如果具有性质A的事件有的事件有m个，性质个，性质B的事件有的事件有 n个，则具有性质个，则具有性质A或或B的事件有的事件有m+n个。个。 A和和B是性质无关的两个事件。是性质无关的两个事件。 9 2、乘法法则、乘法法则: 若具有性质若具有性质A的事件有的事件有m个，具有性质个，具有性质B的事件的事件 有有n个，则具有个，则具有性质性质A及及B的事件有的事件有mn个个 1.1基本计数法则基本计数法则 10 例例1.1 若从合肥到南京有若从合肥到南京有2条路可走，从南京到条路可走，从南京到 上海有上海有3条路

5、可走，从上海到杭州有条路可走，从上海到杭州有2条路可走，条路可走， 问从合肥经南京、上海到杭州有多少路可走？问从合肥经南京、上海到杭州有多少路可走？ 1.1基本计数法则基本计数法则 11 例例1.2：用乘法法则解释：用乘法法则解释8卦及卦及64卦。卦。 解：解：1、太极生两仪、太极生两仪 3 3、四象生八卦、四象生八卦 000，001，010, 011010, 011 100 100，101，110, 111110, 111 2 2、两仪生四象、两仪生四象 00，01，1010，1111； 1.1基本计数法则基本计数法则 12 例例1.31.3：长度为：长度为n n的的0,10,1符号串的数目

6、符号串的数目? ? 例例1.4 1.4 人类人类DNADNA链的长度为链的长度为2.12.1101010 10, ,链上 链上 每一位由每一位由T,C,A,GT,C,A,G四种化合物组成四种化合物组成, ,求人类求人类DNADNA链链 的可组成数目。的可组成数目。 1.1基本计数法则基本计数法则 13 例例1.51.5：求布尔函数：求布尔函数f(xf(x1 1,x,x2 2,x,xn n) )的数目的数目 以以n=2n=2为例：为例： f(xf(x1 1,x,x2 2) )有四种方式：有四种方式： f(0,0),f(0,1),f(1,0),f(1,1)f(0,0),f(0,1),f(1,0),

7、f(1,1)。 1 1、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=0f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=0。 2 2、f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1f(0,0)=0,f(0,1)=0,f(1,0)=0,f(1,1)=1。 对应着长度为对应着长度为2 22 2的字符串，每一位都可以取的字符串，每一位都可以取0 0或或1;1; 乘法：乘法：2 2 2 22 2自变量数为自变量数为n n个时：个时：2 2 2 2n n 1.1基本计数法则基本计数法则 * 14 1 1、从、从n n个数中找出最大值问题个

8、数中找出最大值问题 2 2、n n个人参加单淘汰赛，最后产生冠军的个人参加单淘汰赛，最后产生冠军的 过程。过程。 1.2 一一对应一一对应 15 例例1.61.6：求：求n n2 2个人站成一排和站成个人站成一排和站成n n排（方阵）排（方阵） 的方案数，并比较两种方案数的大小？的方案数，并比较两种方案数的大小？ 解：解：9 9个人站成一排的方案数是个人站成一排的方案数是9!9!， 设设a a1 1a a2 2a a3 3a a4 4a a5 5a a6 6a a7 7a a8 8a a9 9是是9 9个人的一排，个人的一排， 可构成一个方阵可构成一个方阵 a a1 1a a2 2a a3 3

9、 a a4 4a a5 5a a6 6 a a7 7a a8 8a a9 9 给定一个方阵给定一个方阵 b b1 1b b2 2b b3 3 b b4 4b b5 5b b6 6 b b7 7b b8 8b b9 9 也唯一确定一排也唯一确定一排b b1 1b b2 2b b3 3b b4 4b b5 5b b6 6b b7 7b b8 8b b9 9 因此这两种站位方式的方案数一样多，都是因此这两种站位方式的方案数一样多，都是9!9! 1.2 一一对应一一对应 16 例例1.61.6：求：求n n2 2个人站成一排和站成个人站成一排和站成n n排（方阵）排（方阵） 的方案数，并比较两种方案数

10、的大小？的方案数，并比较两种方案数的大小？ 9 9个人站成方阵的方案数为：个人站成方阵的方案数为： C(9,3)3!C(6,3)3!C(3,3)3!C(9,3)3!C(6,3)3!C(3,3)3! ! 9! 3! 3 ! 3 ! 3 ! 6 ! 3 ! 3 ! 6 ! 9 1.2 一一对应一一对应 17 定理定理1.1 n1.1 n个有标号个有标号1,2,n1,2,n的顶点的树的顶点的树 的数目等于的数目等于n nn-2 n-2。（ 。（n=2n=2） 1 2 5 34 设一棵树的顶点集为设一棵树的顶点集为A A 1 1、从中找到编号最小的、从中找到编号最小的 叶子结点，去掉该叶子结点叶子结点

11、，去掉该叶子结点a a1 1 及其邻接边及其邻接边(a(a1 1,b,b1 1) )。 2 2、重复以上过程。只到、重复以上过程。只到 剩一条边为止。剩一条边为止。 (1,2),(4,3),(3,2) (1,2),(4,3),(3,2) 这棵树对应序列（这棵树对应序列（2 2，3 3，2 2） 一个棵对应序列一个棵对应序列B=bB=b1 1b b2 2b b3 3bbn-2 n-2而且是唯一的 而且是唯一的 1.2 一一对应一一对应 18 1 2 5 34 树的顶点集合为树的顶点集合为12345 12345 这棵树对应序列（这棵树对应序列（2 2，3 3，2 2） 任给一个序列任给一个序列Bb

12、Bb1 1,b,b2 2,b,b3 3,b,bn-2 n-2 1 1、从、从A A找到最小的不属于找到最小的不属于B B的元素的元素, ,设为设为a a1 1, ,与与b b1 1连连 接，从接，从A A中去掉中去掉a a1 1，从，从B B中去掉中去掉b b1 1. . 2 2、重复以上过程只到、重复以上过程只到B B为空，为空，A A中剩余两个中剩余两个 3 3、连接剩余的两个顶点。、连接剩余的两个顶点。 1.2 一一对应一一对应 * 19 1.3：排列与组合：排列与组合 1 1、排列的定义：设、排列的定义：设A=aA=a1 1,a,a2 2,a,an n 是是n n个不个不 同的元素的集

13、合，任取同的元素的集合，任取A A中中r r个元素按顺序排成一个元素按顺序排成一 列，称为从列，称为从A A中取中取r r个的一个排列，个的一个排列，r r满足满足0rn0rn。 从从n n个不同的球中取一个球放在第一个盒子中，个不同的球中取一个球放在第一个盒子中， 从余下的从余下的n-1n-1个球中取一个球放在第二个盒子中，个球中取一个球放在第二个盒子中， 从余下的从余下的n-(r-1)n-(r-1)个球中取一个放在第个球中取一个放在第r r个盒子中。个盒子中。 (1)(1)(2)(2)(3)(3)()()(r)(r) 根据乘法法则：根据乘法法则： P(n,r)=n(n-1)(n-r+1)=

14、n!P(n,r)=n(n-1)(n-r+1)=n!(n-r)!(n-r)! 20 全排列全排列:P(n,n)=n(n-1)2:P(n,n)=n(n-1)21=n!1=n! 1.3：排列与组合：排列与组合 2、组合的定义：当从、组合的定义：当从n个不同元素中取出个不同元素中取出r个个 而不考虑它的顺序时而不考虑它的顺序时,称为从称为从n中取中取r个的组合个的组合, 其数目记为其数目记为C(n,r)。 公式：从公式：从n中取中取r的组合数记作的组合数记作C(n,r) 从从n中取中取r的排列数是的排列数是P(n,r)。 C(n,r)=P(n,r)/r! =n!/r!(n-r)! 二者之间的关系二者之

15、间的关系: 21 第一章：排列与组合第一章：排列与组合 排列可以看作排列可以看作n个不同的元素取个不同的元素取r个放进个放进r 个不同的盒子的放法个不同的盒子的放法. 组合可以看作组合可以看作n个不同的元素个不同的元素取取r个个放进放进r个个 相同的盒子的放法相同的盒子的放法. 公式公式1：C(n,r)=C(n,n-r) 22 从从5 5个元素中取个元素中取3 3个进行排列的算法：个进行排列的算法： int a5=1,2,3,4,5,b3int a5=1,2,3,4,5,b3； for(i=0;i5;i+)for(i=0;i5;i+) b0=ai; b0=ai; for(j=0;j5;j+)

16、for(j=0;j5;j+) if (j=i) continue; if (j=i) continue; else b1=aj; else b1=aj; for(k=0;k5;k+) for(k=0;k5;k+) if(k=i|k=j) continue; if(k=i|k=j) continue; else b2=ak; else b2=ak; 打印打印bb 1.3：排列与组合：排列与组合 23 例例1.7:1.7:由由5 5种颜色的星状物种颜色的星状物,20,20种不同的花共种不同的花共2525 个元素中任取个元素中任取5 5个排成如下图案：两边是星状物个排成如下图案：两边是星状物, ,中

17、中 间是间是3 3朵花，问共有多少种这样的图案？朵花，问共有多少种这样的图案？ 解解1 1：5 52020191918184=136800 4=136800 2020种不同的花取种不同的花取3 3种排列的排列数为：种排列的排列数为： P(20,3)=20!/17!=20P(20,3)=20!/17!=20* *1919* *18=684018=6840 根据乘法法则，共有图案数为：根据乘法法则，共有图案数为： 68406840* *20=13680020=136800 解解2 2：5 5种颜色的星状物取两个排列的排列数为种颜色的星状物取两个排列的排列数为 P(5,2)=5!/3!=5P(5,2

18、)=5!/3!=5* *4=20 4=20 1.3：排列与组合：排列与组合 24 1.8 1.8 随机地选择随机地选择n n个人，求个人，求n n个人至少有两人生个人至少有两人生 日相同的概率日相同的概率( (不考虑润年不考虑润年) ) 解解: : n n个人生日不同的方案数是个人生日不同的方案数是: : 365 365* *364364* * *(365-n+1)=P(365,n)(365-n+1)=P(365,n) n n个人生日的总方案数是个人生日的总方案数是: : 365 365n n 至少有两人生日相同的概率至少有两人生日相同的概率: : 1-P(365,n)/365 1-P(365

19、,n)/365n n 1.3：排列与组合：排列与组合 25 1.8 1.8 随机地选择随机地选择n n个人，求个人，求n n个人至少有两人生个人至少有两人生 日相同的概率日相同的概率( (不考虑润年不考虑润年) ) 解解: : 思路：任选两人，使其生日相同，其它任选。思路：任选两人，使其生日相同，其它任选。 至少有两人生日相同的概率至少有两人生日相同的概率: : C(365,1) C(365,1)C(n,2)C(n,2)365365n-2 n-2/365 /365n n 1.3：排列与组合：排列与组合 * 对还是错？对还是错？ 26 1.4：圆周排列：圆周排列 定义：在排列中，如果我们不横排而

20、是定义：在排列中，如果我们不横排而是 将各元素排列在一个圆周上，那么我们称这种将各元素排列在一个圆周上，那么我们称这种 排列方式为圆周排列。排列方式为圆周排列。 在排列中在排列中1234,2341,3412,41231234,2341,3412,4123为四个不为四个不 同的排列，而在圆排列中这些排列是一个同的排列，而在圆排列中这些排列是一个. . 规定相对位置不变算一个排列。规定相对位置不变算一个排列。 27 将从将从n n中取中取r r个作圆排列的排列数记作个作圆排列的排列数记作Q(n,r)Q(n,r)。 从从n n中取中取r r个作排列，与圆排列相比，重复了个作排列，与圆排列相比，重复了

21、r r倍；倍； 公式：公式：Q(n,r)=P(n,r)/rQ(n,r)=P(n,r)/r， Q(n,n)=P(n,n)/n=n!/n=(n-1)!Q(n,n)=P(n,n)/n=n!/n=(n-1)! 1.4：圆周排列：圆周排列 Q(n,r)=P(n,r)/r=n!/r(n-r)!Q(n,r)=P(n,r)/r=n!/r(n-r)! 28 例例1.191.19：5 5颗不同的红色珠子，颗不同的红色珠子，3 3颗不同的蓝颗不同的蓝 色珠子装在圆板的四周色珠子装在圆板的四周, ,试问有多少种方案？若蓝试问有多少种方案？若蓝 色珠子不相邻又有多少种排列方案？蓝色珠子在色珠子不相邻又有多少种排列方案？

22、蓝色珠子在 一起又如何？一起又如何？ 解：解：(1)Q(8,8)=P(8,8)/8=7!(1)Q(8,8)=P(8,8)/8=7!。 (3) (3)蓝色珠子在一起蓝色珠子在一起 Q(6,6)3!=5!3!Q(6,6)3!=5!3!。 (2) (2) 蓝色珠子不在一起。蓝色珠子不在一起。 首先首先5 5颗不同的红色珠子作圆排列，共有颗不同的红色珠子作圆排列，共有 Q(5,5)=4!Q(5,5)=4!， 3 3颗不同的蓝色珠子排在红色珠子中间颗不同的蓝色珠子排在红色珠子中间 4! 4!5 54 43 3 1.4：圆周排列：圆周排列 * 29 例例1.201.20：5 5对夫妇出席一宴会，围一圆桌对

23、夫妇出席一宴会，围一圆桌 而坐，试问有几种不同的方案？若要求每对而坐，试问有几种不同的方案？若要求每对 夫妻相邻又有多少种方案夫妻相邻又有多少种方案? ? 解：解： 1 1）座位无限制）座位无限制 Q(10,10)=P(10,10)/10=10!/10=9!=362880Q(10,10)=P(10,10)/10=10!/10=9!=362880 共有共有362880362880种方式。种方式。 2 2）夫妇相邻而坐）夫妇相邻而坐 首先可以将一对夫妇作为一个元素来看待，首先可以将一对夫妇作为一个元素来看待， 共有共有Q(5,5)=P(5,5)/5=24Q(5,5)=P(5,5)/5=24。 但夫

24、妇可以交换坐位，但夫妇可以交换坐位，5 5对夫妇共有对夫妇共有2 25 5种方式。种方式。 根据乘法法则：若夫妻相邻而坐，共根据乘法法则：若夫妻相邻而坐，共 有有 24242 25 5=24=2432=76832=768种方式。种方式。 1.4：圆周排列：圆周排列 * 30 第一章：排列与组合第一章：排列与组合 多重集的排列多重集的排列 设设S S是一个多重集，有是一个多重集，有K K个不同类型的元素，个不同类型的元素， 各元素的重复分别为各元素的重复分别为n n1 1,n,n2 2,n,nk k,n=n,n=n1 1+n+n2 2+n+nk k, , 则则S S的排列数为的排列数为: : !

25、.! ! 21k nnn n 31 第一章：排列与组合第一章：排列与组合 证明：给定多重集证明：给定多重集S S，有，有k k种类型的元素，比种类型的元素，比 如说如说a a1 1,a,a2 2,a,a3 3,a,ak k, ,且分别有重数且分别有重数n n1 1,n,n2 2,n,nk k, , 元素的总个数元素的总个数n=nn=n1 1+n+n2 2+n+nk k, , 现在存在现在存在n n个位置个位置, ,我们要在我们要在n n个位置放个位置放S S的一的一 个元素个元素, ,首先要确定哪些位置放首先要确定哪些位置放a a1 1的元素的元素, ,共共 有有 1 n n C 剩下剩下n-

26、nn-n1 1个位置个位置, a, a2 2的元素的元素, ,共有共有 2 1 n nn C . 剩下剩下n-nn-n1 1-n-nk-1 k-1个位置 个位置, a, ak k的元素的元素, ,共有共有 k k n nnn C 11 . 32 第一章：排列与组合第一章：排列与组合 根据剩法法则根据剩法法则: : S S的排列的总数的排列的总数 k k n nnn n nnn n nn n n CCCC 11 3 21 2 1 1 . . . !)!( )!( !)!( )!( !)!( ! 3321 21 221 1 11 nnnnn nnn nnnn nn nnn n !)!( )!.(

27、21 121 kk k nnnnn nnnn !.! ! 21k nnn n 33 练习题练习题 1、求、求1040和和2030的公因数的数目。的公因数的数目。 解：解：1040=240540，2030=260530 C(41,1)*C(31,1) 34 2 2、试证、试证n n2 2的整除数的数目是奇数。的整除数的数目是奇数。 m a m aa pppn. 21 21 m a m aa pppn 22 2 2 1 2 . 21 ) 1 , 12(.) 1 , 12() 1 , 12( 21 m aCaCaC 练习题练习题 35 1.13 1.13、有、有n n个不同的整数，从中取出两组来，个不同的整数，从中取出两组来， 要求第要求第1 1组的最小数大于另一组的最大数。组的最小数大于另一组的最大数。 设取的第一组数有设取的第一组数有a a个个, ,第二组有第二组有b b个个, , 要求第一组数中最小数大于第二组中最大的，要求第一组数中最小数大于第二组中最大的， 即只要取出一组即只要取出一组m m个数个数( (设设m=a+b),m=a+b),从大到小从大到小 取取a a个作为第一组个作为第一组, ,剩余的为第二组。剩余的为第二组。 此时方案数为此时方案数为C(n,m)C(n,m)。 从从m m个数中取第一组数共有个数中取第一组数共有m-1m-1中取法。中取法。 (m-