1、1组合数学组合数学课时：课时：36学时学时 成绩分配：平时成绩成绩分配：平时成绩30分，期末考分，期末考试成绩试成绩70分。分。 平时成绩取得方式：安排平时成绩取得方式：安排5次课堂次课堂测验，每次测验，每次6分。分。 课件邮箱课件邮箱: 密码密码:200708262组合数学的应用范畴组合数学的应用范畴从广义上讲组合数学就是离散数学从广义上讲组合数学就是离散数学 组合数学研究满足一定条件的组合模型的组合数学研究满足一定条件的组合模型的情况情况: (1)存在性：存在性： (2)计数：计数： (3)有哪些？有哪些？ (4)哪些最优？哪些最优？ 组合数学与组合数学与算法、算法、密码学、编码理论、数密
2、码学、编码理论、数据压缩等计算机方向密据压缩等计算机方向密不可分。不可分。*3选用教材选用教材组合数学组合数学(第四版第四版)卢开澄卢开澄 卢华明卢华明 著著清华大学出版社清华大学出版社4组合数学的应用范畴组合数学的应用范畴 第一章第一章:排列与组合排列与组合 第二章第二章:递推关系与母函数递推关系与母函数 第三章第三章:容斥原理与鸽巢原理容斥原理与鸽巢原理 第四章第四章:Burnside引理与引理与Polya定理定理 第五章第五章:区组设计区组设计 第六章第六章:线性规划线性规划 第七章第七章:编码简介编码简介 第八章第八章:组合算法简介组合算法简介 5参考教材参考教材组合数学组合数学Ric
3、hard A. Brualdi 著著冯舜玺等译冯舜玺等译机械工业出版社机械工业出版社6参考教材参考教材组合数学及其算法组合数学及其算法杨振生杨振生中国科学技术大学出版社中国科学技术大学出版社7第一章：排列与组合第一章：排列与组合1.1 基本计数法则基本计数法则1.2 一一对应一一对应:1.3 排列与组合排列与组合1.4 圆周排列圆周排列1.5 排列的生成算法排列的生成算法1.6 允许重复的组合与不相邻的组合允许重复的组合与不相邻的组合1.7 组合意义的解释组合意义的解释1.8 应用举例应用举例1.9 *Stirling公式公式81.1基本计数法则基本计数法则1、加法法则、加法法则:如果具有性质
4、如果具有性质A的事件有的事件有m个，性质个，性质B的事件有的事件有n个，则具有性质个，则具有性质A或或B的事件有的事件有m+n个。个。A和和B是性质无关的两个事件。是性质无关的两个事件。92、乘法法则、乘法法则:若具有性质若具有性质A的事件有的事件有m个，具有性质个，具有性质B的事件的事件有有n个，则具有个，则具有性质性质A及及B的事件有的事件有mn个个1.1基本计数法则基本计数法则10例例1.1 若从合肥到南京有若从合肥到南京有2条路可走，从南京到条路可走，从南京到上海有上海有3条路可走，从上海到杭州有条路可走，从上海到杭州有2条路可走，条路可走，问从合肥经南京、上海到杭州有多少路可走？问从
5、合肥经南京、上海到杭州有多少路可走？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符号串的数目符号串的数目? ? 例例1.4 1.4 人类人类DNADNA链的长度为链的长度为2.12.110101010, ,链上链上
6、每一位由每一位由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),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
7、)=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 n1.1基本计数法则基本计数法则*14 1 1、从、从n n个数中找出最大值问题个数中找出最大值问题 2 2、n n个人参加单淘汰赛，最后产生冠军的个人参加单淘汰赛，最后产生冠军的过程。过程。1.2 一一对应一一对应15例例1.61.
8、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 3a a4 4a a5 5a a6 6a a7 7a a8 8a a9 9给定一个方阵给定一个方阵b b1 1b b2 2b b3 3b b4 4b b5 5b b6 6
9、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排（方阵）排（方阵）的方案数，并比较两种方案数的大小？的方案数，并比较两种方案数的大小？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!
10、 9! 3! 3! 3 ! 3! 6! 3! 3 ! 6! 91.2 一一对应一一对应17 定理定理1.1 n1.1 n个有标号个有标号1,2,1,2,n,n的顶点的树的顶点的树的数目等于的数目等于n nn-2n-2。（。（n=2n=2）12534 设一棵树的顶点集为设一棵树的顶点集为A A 1 1、从中找到编号最小的、从中找到编号最小的叶子结点，去掉该叶子结点叶子结点，去掉该叶子结点a a1 1及其邻接边及其邻接边(a(a1 1,b,b1 1) )。 2 2、重复以上过程。只到、重复以上过程。只到剩一条边为止。剩一条边为止。 (1,2),(4,3),(3,2) (1,2),(4,3),(3,
11、2) 这棵树对应序列（这棵树对应序列（2 2，3 3，2 2） 一个棵对应序列一个棵对应序列B=bB=b1 1b b2 2b b3 3b bn-2n-2而且是唯一的而且是唯一的1.2 一一对应一一对应1812534 树的顶点集合为树的顶点集合为12345 12345 这棵树对应序列（这棵树对应序列（2 2，3 3，2 2） 任给一个序列任给一个序列BbBb1 1,b,b2 2,b,b3 3, ,b,bn-2n-2 1 1、从、从A A找到最小的不属于找到最小的不属于B B的元素的元素, ,设为设为a a1 1, ,与与b b1 1连连接，从接，从A A中去掉中去掉a a1 1，从，从B B中去
12、掉中去掉b b1 1. . 2 2、重复以上过程只到、重复以上过程只到B B为空，为空，A A中剩余两个中剩余两个 3 3、连接剩余的两个顶点。、连接剩余的两个顶点。1.2 一一对应一一对应*191.3：排列与组合：排列与组合 1 1、排列的定义：设、排列的定义：设A=aA=a1 1,a,a2 2, ,a,an n 是是n n个不个不同的元素的集合，任取同的元素的集合，任取A A中中r r个元素按顺序排成一个元素按顺序排成一列，称为从列，称为从A A中取中取r r个的一个排列，个的一个排列，r r满足满足0rn0rn。 从从n n个不同的球中取一个球放在第一个盒子中，个不同的球中取一个球放在第
13、一个盒子中， 从余下的从余下的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)P(n,r)=n(n-1)(n-r+1)=n!(n-r+1)=n!(n-r)!(n-r)!20全排列全排列:P(n,n)=n(n-1):P(n,n)=n(n-1)2 21=n!1=n!1.3：排列与组合：排列与组合2、组合的定义：当从、组合的定义：当从n个不同元素中取
14、出个不同元素中取出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)!二者之间的关系二者之间的关系:21第一章：排列与组合第一章：排列与组合 排列可以看作排列可以看作n个不同的元素取个不同的元素取r个放进个放进r个不同的盒子的放法个不同的盒子的放法. 组合可以看作组合可以看作n个不同的元素个不同的元素取取r个个放进放进r个个相同的盒子的放法相同的盒子的放法
15、.公式公式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(ifor(i=0;i5;i+)=0;i5;i+) b0=ai b0=ai; for(j for(j=0;j5;j+)=0;j5;j+) if (j=i) continue; if (j=i) continue; else b1=aj else b1=aj; for(k for(k=0;k5;k+)=0;k5;k+) if(k=i|k if(k=i|k=j) continue;=j) c
16、ontinue; else b2=ak else b2=ak; 打印打印bb1.3：排列与组合：排列与组合23 例例1.7:1.7:由由5 5种颜色的星状物种颜色的星状物,20,20种不同的花共种不同的花共2525个元素中任取个元素中任取5 5个排成如下图案：两边是星状物个排成如下图案：两边是星状物, ,中中间是间是3 3朵花，问共有多少种这样的图案？朵花，问共有多少种这样的图案？ 解解1 1：5 52020191918184=136800 4=136800 2020种不同的花取种不同的花取3 3种排列的排列数为：种排列的排列数为：P(20,3)=20!/17!=20P(20,3)=20!/1
17、7!=20* *1919* *18=684018=6840根据乘法法则，共有图案数为：根据乘法法则，共有图案数为：68406840* *20=13680020=136800解解2 2：5 5种颜色的星状物取两个排列的排列数为种颜色的星状物取两个排列的排列数为 P(5,2)=5!/3!=5P(5,2)=5!/3!=5* *4=20 4=20 1.3：排列与组合：排列与组合24 1.8 1.8 随机地选择随机地选择n n个人，求个人，求n n个人至少有两人生个人至少有两人生日相同的概率日相同的概率( (不考虑润年不考虑润年) ) 解解: : n n个人生日不同的方案数是个人生日不同的方案数是: :
18、 365365* *364364* * *(365-n+1)=P(365,n)(365-n+1)=P(365,n) n n个人生日的总方案数是个人生日的总方案数是: : 365365n n 至少有两人生日相同的概率至少有两人生日相同的概率: : 1-P(365,n)/365 1-P(365,n)/365n n1.3：排列与组合：排列与组合25 1.8 1.8 随机地选择随机地选择n n个人，求个人，求n n个人至少有两人生个人至少有两人生日相同的概率日相同的概率( (不考虑润年不考虑润年) ) 解解: : 思路：任选两人，使其生日相同，其它任选。思路：任选两人，使其生日相同，其它任选。 至少有
19、两人生日相同的概率至少有两人生日相同的概率: : C(365,1) C(365,1)C(n,2)C(n,2)365365n-2n-2/365/365n n1.3：排列与组合：排列与组合* 对还是错？对还是错？261.4：圆周排列：圆周排列 定义：在排列中，如果我们不横排而是定义：在排列中，如果我们不横排而是将各元素排列在一个圆周上，那么我们称这种将各元素排列在一个圆周上，那么我们称这种排列方式为圆周排列。排列方式为圆周排列。 在排列中在排列中1234,2341,3412,41231234,2341,3412,4123为四个不为四个不同的排列，而在圆排列中这些排列是一个同的排列，而在圆排列中这些
20、排列是一个. . 规定相对位置不变算一个排列。规定相对位置不变算一个排列。27将从将从n n中取中取r r个作圆排列的排列数记作个作圆排列的排列数记作Q(n,r)Q(n,r)。从从n n中取中取r r个作排列，与圆排列相比，重复了个作排列，与圆排列相比，重复了r r倍；倍；公式：公式：Q(n,r)=P(n,r)/rQ(n,r)=P(n,r)/r，Q(n,nQ(n,n)=P(n,n)/n=n!/n=(n-1)!)=P(n,n)/n=n!/n=(n-1)!1.4：圆周排列：圆周排列Q(n,r)=P(n,r)/r=n!/r(n-rQ(n,r)=P(n,r)/r=n!/r(n-r)!)!28 例例1.
21、191.19：5 5颗不同的红色珠子，颗不同的红色珠子，3 3颗不同的蓝颗不同的蓝色珠子装在圆板的四周色珠子装在圆板的四周, ,试问有多少种方案？若蓝试问有多少种方案？若蓝色珠子不相邻又有多少种排列方案？蓝色珠子在色珠子不相邻又有多少种排列方案？蓝色珠子在一起又如何？一起又如何？ 解：解：(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颗不同的红色珠子作圆排列，共有颗不同的红色珠子作圆排列
22、，共有 Q(5,5)=4!Q(5,5)=4!， 3 3颗不同的蓝色珠子排在红色珠子中间颗不同的蓝色珠子排在红色珠子中间 4! 4!5 54 43 31.4：圆周排列：圆周排列*29 例例1.201.20：5 5对夫妇出席一宴会，围一圆桌对夫妇出席一宴会，围一圆桌而坐，试问有几种不同的方案？若要求每对而坐，试问有几种不同的方案？若要求每对夫妻相邻又有多少种方案夫妻相邻又有多少种方案? ? 解：解： 1 1）座位无限制）座位无限制 Q(10,10)=P(10,10)/10=10!/10=9!=362880Q(10,10)=P(10,10)/10=10!/10=9!=362880 共有共有36288
23、0362880种方式。种方式。 2 2）夫妇相邻而坐）夫妇相邻而坐 首先可以将一对夫妇作为一个元素来看待，首先可以将一对夫妇作为一个元素来看待，共有共有Q(5,5)=P(5,5)/5=24Q(5,5)=P(5,5)/5=24。 但夫妇可以交换坐位，但夫妇可以交换坐位，5 5对夫妇共有对夫妇共有2 25 5种方式。种方式。 根据乘法法则：若夫妻相邻而坐，共根据乘法法则：若夫妻相邻而坐，共有有 24242 25 5=24=2432=76832=768种方式。种方式。 1.4：圆周排列：圆周排列*30第一章：排列与组合第一章：排列与组合 多重集的排列多重集的排列 设设S S是一个多重集，有是一个多重
24、集，有K K个不同类型的元素，个不同类型的元素，各元素的重复分别为各元素的重复分别为n n1 1,n,n2 2, ,n,nk k,n,n=n=n1 1+n+n2 2+ +n+nk k, ,则则S S的排列数为的排列数为: :!.!21knnnn31第一章：排列与组合第一章：排列与组合 证明：给定多重集证明：给定多重集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, , 现
25、在存在现在存在n n个位置个位置, ,我们要在我们要在n n个位置放个位置放S S的一的一个元素个元素, ,首先要确定哪些位置放首先要确定哪些位置放a a1 1的元素的元素, ,共共有有1nnC 剩下剩下n-nn-n1 1个位置个位置, a, a2 2的元素的元素, ,共有共有21nnnC. . 剩下剩下n-nn-n1 1- -n-nk-1k-1个位置个位置, a, ak k的元素的元素, ,共有共有kknnnnC11.32第一章：排列与组合第一章：排列与组合 根据剩法法则根据剩法法则: : S S的排列的总数的排列的总数kknnnnnnnnnnnnnCCCC11321211.!)!()!(!
26、)!()!(!)!(!332121221111nnnnnnnnnnnnnnnnnn!)!()!.(21121kkknnnnnnnnn!.!21knnnn33练习题练习题 1、求、求1040和和2030的公因数的数目。的公因数的数目。 解：解：1040=240540，2030=260530C(41,1)*C(31,1)342 2、试证、试证n n2 2的整除数的数目是奇数。的整除数的数目是奇数。mamaapppn.2121mamaapppn222212.21) 1 , 12(.) 1 , 12() 1 , 12(21maCaCaC练习题练习题35 1.13 1.13、有、有n n个不同的整数，从
27、中取出两组来，个不同的整数，从中取出两组来，要求第要求第1 1组的最小数大于另一组的最大数。组的最小数大于另一组的最大数。设取的第一组数有设取的第一组数有a a个个, ,第二组有第二组有b b个个, ,要求第一组数中最小数大于第二组中最大的，要求第一组数中最小数大于第二组中最大的，即只要取出一组即只要取出一组m m个数个数( (设设m=a+bm=a+b),),从大到小从大到小取取a a个作为第一组个作为第一组, ,剩余的为第二组。剩余的为第二组。此时方案数为此时方案数为C(n,mC(n,m) )。从从m m个数中取第一组数共有个数中取第一组数共有m-1m-1中取法。中取法。(m-1)C(n,m
28、)(m-1)C(n,m)练习题练习题36nmnnmnCm2112),() 1(练习题练习题*37第第1 1章：游戏中碰到的题目：章：游戏中碰到的题目：1 1、中国象棋将帅问题、中国象棋将帅问题2 2、一摞烙饼的排序、一摞烙饼的排序3 3、买书问题、买书问题4 4、快速找出故障机器、快速找出故障机器5 5、饮料供货、饮料供货6 6、光影切割问题、光影切割问题7 7、小飞的电梯调度算法、小飞的电梯调度算法8 8、高效率地安排见面会、高效率地安排见面会9 9、双线程高效下载、双线程高效下载.编程之美编程之美-微软技术面试心得微软技术面试心得38编程之美编程之美-微软技术面试心得微软技术面试心得第第2
29、 2章：数字之魅章：数字之魅1 1、求二进制数中、求二进制数中1 1的个数的个数2 2、不要被阶乘吓倒、不要被阶乘吓倒3 3、寻找发帖、寻找发帖“水王水王”4 4、1 1的数目的数目5 5、寻找最大的、寻找最大的K K个数个数6 6、最大公约数问题、最大公约数问题7 7、找符合条件的整数、找符合条件的整数8 8、斐波那契（、斐波那契（FibonacciFibonacci）数列）数列.39编程之美编程之美-微软技术面试心得微软技术面试心得第第3 3章结构之法章结构之法1 1、字符串移位包含的问题、字符串移位包含的问题2 2、电话号码对应英语单词、电话号码对应英语单词3 3、计算字符串的相似度、计算字符串的相似度4 4、从无头单链表中删除节点、从无头单链表中删除节点5 5、最短摘要的生成、最短摘要的生成.8 8、求二叉树中节点的最大距离、求二叉树中节点的最大距离9 9、重建二叉树、重建二叉树1010、分层遍历二叉树、分层遍历二叉树40编程之美编程之美-微软技术面试心得微软技术面试心得第第4 4章数学之趣章数学之趣1 1、金刚坐飞机问题、金刚坐飞机问题2 2、瓷砖覆盖地板、瓷砖覆盖地板3 3、买票找零、买票找零4 4、点是否在三角形内、点是否在三角形内5 5、桶中取黑白球、桶中取黑白球6 6、蚂蚁爬杆、蚂蚁爬杆. . *
