组合数学1课件

1、ACM暑期集训之组合数学,刘昆 2009年8月,主要研究内容,依据一定的规则来安排某些事物的有关数学问题，这些问题包括4个方面： 这种安排是否存在，即存在性问题； 如果符合要求的安排是存在的，那么这样的安排又有多少，即计数问题（包括枚举的验证与效率）； 怎样构造这种安排，即算法构造问题； 如果给出了最优化标准，又怎样得到最优安排，即最优化问题。,组合问题的基本解题方法,从组合学基本概念、基本原理出发的所谓常规方法 通常与问题所涉及的组合数学概念无关的非常规方法 数学归纳法 一一对应技术（8个“车”问题） 殊途同归方法（C(n,0)+C(n,n)=2n） 数论方法（n位客人握手） 回溯法,内容提

2、要,排列组合 鸽巢原理 递推关系与生成函数 二分图的最大匹配 Polya计数原理的相关数学基础,排列组合,两个基本原则,1、加法原则 如果完成一件事情有两种方案，而第一个方案有m种方法，第二个方案有n中方法，则完成该事情共有m+n种方法。 2、乘法原则 如果完成一件事情需要两个步骤，第一步有m中方法，第二步又有n种方法，则完成该事情共有m*n种方法,排列组合的几个基本结论,相异元素不允许重复的排列数和组合数： 不尽相异元素的全排列,排列组合的几个基本结论,相异元素不允许重复的圆排列 相异元素允许重复的组合数,集合描述：设S=e1, e2, en,，从S中允许重复地取出r个元素，称为r可重组合,

3、圆排列,6位女士和6位先生围着一张圆桌聚餐，要求安排女士和先生交替就座。问：有多少可能的安排方案。 解. 由于要求安排女士和先生交替就座，因此可以先安排六位女士坐下，两位之间留出一个空位，然后再安排先生就座。安排六位女士坐下（圆排列）的方案数是 （种）,圆排列（续）,由于已经有女士在位，安排先生在六个空位上就座时，就不再是圆排列了，因为原先被看成相同圆排列的六位先生的就座方式所产生的全体人员的圆排列是不同的。故安排先生在六个空位上就座的方案数是 6！720 于是我们得到满足要求安排方案共计有,电子锁,某机要部门安装了电子锁。M工作人员每人发一张磁卡，卡上有开锁的密码特征，为了确保安全，规定至少

4、有N人同时使用各自的磁卡才能将锁打开。 现在需要计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少要有多少特征,电子锁（续）,先做一个简单的假设：M=7，N=4。,对于问题一：任意3人在一起，至少缺一种特征，不能打开。,电子锁的至少应有C(7,3)=35种特征。,对于问题二：对任一位工作者的磁卡而言，其 余6人中任意3人在场至少缺少一种A所具有的特征 而无法打开大门。,所以总终答案是C(M,N-1)和C(M-1,N-1),电子锁（续）,电子锁（续）,电子锁（续）,电子锁（续）,zju1976 Path On a Grid,求n*m的方格图形中，从点（0，0）到点（n，m）的最短路径数目,

5、（n，m）,Sample Input （给定n，m） 5 41 10 0 Sample Output (路径数目) 1262,（0，0）,Path On a Grid（续）,我们用组合数学的思路来解题。最短路径必定是一条只向右上走得路。设向右走一步为x，向上走一步为y。则每一条路线一定对应由n个x，m个y共m+n个元素组成的排列。,以n=5，m=4为例，,任意一条路线如下图所示，对应的xy序列 为：xyxxxyxyy,可见，只要能确定9个位置中4个y的位置 就唯一确定了一条路径。,所以，本题答案就是C(n+m,m),排列组合数的一般计算方法,怎么计算？设计一个求阶乘的函数？,20！= 2432

6、902008176640000 12！= 479001600 8！ = 40320 C(20,12) = 125970,显然20！用int表示一定是失败的，而C(20,12)的结果又完全 可以用int来表示。,回想我们是怎么计算的?,先约分再计算！,代码,int gcd(int a, int b) if(b=0)return a; else return gcd(b,a%b); /欧几里德辗转相除法求最大公约数,int C(int n ,int m) int i,a,fz=1,fm=1;,for( i = 1; i = m ;i+) fz*=(n-i+1); fm*=i; a = gcd(fz

7、,fm); fz/=a; fm/=a; return fz/fm; ,分子,分母,全排列生成算法,如果将整数n从1，2。，n的一个排列中删除，那么结果则是1，2。，n-1的一个排列。 给定一个1，2。，n-1的排列，只要将n插入到其中的n个间隔（含头尾） 算法描述： 从1开始，将2插入排列中得1，2的排列，以此类推，直至得到1，2。，n的排列,1，2，3全排列生成算法示例,1 2 21 1 2 3 1 3 2 3 1 2 2 1 3 2 3 1 3 2 1,STL中生成排列数的函数,#include int A = 2, 3, 4, 5, 6, 1; prev_permutation(A, A

8、+6); 结果：234516 int A = 2, 3, 4, 5, 6, 1; next_permutation(A, A+6); 结果：234615,组合的生成算法,Zju1089 有n(n=6)个数字，要求按字典序输出所有从该n个数字中取6个的组合。,Sample Input 7 1 2 3 4 5 6 7 8 1 2 3 5 8 13 21 34 0,Sample Output 1 2 3 4 5 6 1 2 3 4 5 7 1 2 3 4 6 7 1 2 3 5 6 7,1 2 4 5 6 7 1 3 4 5 6 7 2 3 4 5 6 7 1 2 3 5 8 13 1 2 3 5

9、8 21 1 2 3 5 8 34 1 2 3 5 13 21 ,n,组合的生成算法（续）,Code:,#include #include #include using namespace std; int k; int used13; int lotto13; void output(); void choosenext(int I , int num);,int main() int n_case = 0, i; while(cink,组合的生成算法（续）,void output() int i,n=0; for(i = 0 ;i k ; i +) if(usedi) if(n) cout

10、 ; coutlottoi; n+; coutendl; ,void choosenext(int I , int num) if(num = 6) output(); return ; if(I = k) return ; for(int i = I ;i k ;i +) usedi = 1; choosenext(i+1,num+1); usedi = 0; ,相关练习,NKOJ 1038 NKOJ 1108,鸽巢原理,鸽巢原理之一,鸽巢原理是组合数学中最简单也是最基本 的原理，也叫抽屉原理。即,“若有n个鸽子巢，n+1个鸽子，则至少有 一个巢内有至少有两个鸽子。”,例367人中至少有人的

11、生日相同。 例10双手套中任取11只，其中至少有 两只是完整配对的。 例参加一会议的人中至少有人认识 的别的参加者的人数相等。,鸽巢原理之二,鸽巢原理二m1 , m2 , , mn都是正整数， 并有m1 + m2 + +mnn + 1个鸽子住进n个 鸽巢，则至少对某个 i 有第 i 个巢中至少有 mi个鸽子，i = 1 , 2 , , n,上一小节的鸽巢原理一是这一原理的特殊 情况，即m1 = m2 = = mn= 2， m1 + m2 + +mnn + 1 = n + 1 如若不然，则对任一 i， 都有第 i 个巢中的 鸽子数mi1则,鸽巢原理之二,鸽子总数 m1 + m2 + +mnn ，

12、 与假设相矛盾,推论m只鸽子进n个巢，至少有一个巢 里有 |只鸽子,n,m,推论n(m1) + 1只鸽子进n个巢，至少 有一个巢内至少有m只鸽子,递归关系和生成函数,定义：对于序列 构造一函数：,母函数,称函数G(x)是序列 的母函数,称重问题,假设你现有质量分别为1克、2克和3克的砝码各一枚，问只用这些砝码各一次你能称出哪几种质量？而对每种质量确定的物体又有多少种不同的称量方案？,命题1,若有质量为1，2，3，n克的砝码各1枚，则称重情况的数学模型为： (1+x)(1+x2)(1+xn)，能表示方案总数，但是不能表示具体的称量方案 (1+x1)(1+x22)(1+xnn)，既能表示称量方案总

13、数，又能表示具体的称量方案。,命题2,若有质量为k1，k2，k3，kn克的砝码各1枚，则称重情况的数学模型为： (1+xk1)(1+xk2)(1+xkn)，能表示方案总数，但是不能表示具体的称量方案 (1+x1k1)(1+x2k2)(1+xnkn)，既能表示称量方案总数，又能表示具体的称量方案。,命题3 若有质量为1克的砝码n枚，则称量情况的数学模型为1+x+x2+xn 命题4 若有质量为1克的砝码任意多枚，则称量情况的数学模型为1+x+x2+ 命题5 若有质量为k克的砝码n枚，则称量情况的数学模型为1+xk+x2k+xnk 命题6 若有质量为k克的砝码任意多枚，则称量情况的数学模型为1+xk

14、+x2k+,命题7 若有质量为k1,k2,kn克的砝码各m1,m2,mn枚，则称量情况的数学模型为 (1+xk1+x2k1+xmk1) *(1+xk2+x2k2+xmk2) (1+xkn+x2kn+xmkn)能表示方案总数，但是不能表示称量的具体方案 (1+x1k1+x12k1+x1mk1) *(1+x2k2+x22k2+x2mk2) (1+xnkn+xn2kn+xnmkn)既能表示方案总数，又能表示称量的具体方案,命题8 若有质量为k1,k2,kn克的砝码各任意多枚，则称量情况的数学模型为 (1+xk1+x2k1+) *(1+xk2+x2k2+) (1+xkn+x2kn+)能表示方案总数，但

15、是不能表示称量的具体方案 (1+x1k1+x12k1+) *(1+x2k2+x22k2+) (1+xnkn+xn2kn+)既能表示方案总数，又能表示称量的具体方案,模型应用,某一案件中一共听到4声枪声，已知甲乙丙三个嫌犯各有机会开至多3、2、1枪，试分析谁开这4枪共有多少种可能情况 (1+x1+x12+x3)(1+x2+x22)(1+x3) (3,0,1),(2,1,1),(2,2)(1,2,1)(3,1),命题9 从a1,a2,an这n个不同的元素中取出r(0,1,2,n)个元素的全组合方案的数学模型为(1+a1)(1+a2)(1+an) 命题10 从m个相同的元素a和(n-m)个不同的元素

16、a1,a2,an-m中取出r(0,1,2,n)个元素的全组合方案的数学模型为 (1+a+a2+am)(1+a1)(1+a2)(1+an-m),递推关系,利用递推关系进行计数这个方法在算法分析中经常用到，举例说明如下：,例一.Hanoi问题：这是个组合数学中的著名问题。N个圆盘依其半径大小，从下而上套在A柱上，如下图示。每次只允许取一个移到柱B或C上，而且不允许大盘放在小盘上方。若要求把柱A上的n个盘移到C柱上请设计一种方法来，并估计要移动几个盘次。现在只有A、B、C三根柱子可用。,递推关系,Hanoi问题是个典型的问题，第一步要设计算法，进而估计它的复杂性，集估计工作量。,算法：,N=2时,第

17、一步先把最上面的一个圆盘套在B上, ,第二步把下面的一个圆盘移到C上, ,最后把B上的圆盘移到C上,到此转移完毕,递推关系,对于一般n个圆盘的问题，,假定n-1个盘子的转移算法已经确定。,先把上面的n-1个圆盘经过C转移到B。,第二步把A下面一个圆盘移到C上,最后再把B上的n-1个圆盘经过A转移到C上,递推关系,上述算法是递归的运用。n=2时已给出算法；n=3时，第一步便利用算法把上面两个盘移到B上，第二步再把第三个圆盘转移到柱C上；最后把柱B上两个圆盘转移到柱C上。N=4，5，以此类推。,递推关系,算法分析：令h(n)表示n个圆盘所需要的转移盘次。根据算法先把前面n-1个盘子转移到B上；然后

18、把第n个盘子转到C上；最后再一次将B上的n-1个盘子转移到C上。 n=2时，算法是对的，因此，n=3是算法是对的。以此类推。于是有,递推关系,算法复杂度为：,H(x)是序列 的母函数。给定了序列，对应的母函数也确定了。反过来也一样，求得了母函数，对应的序列也就可得而知了。当然，利用递推关系(2-2-1)式也可以依次求得 ，这样的连锁反应关系，叫做递推关系。,递推关系,下面介绍如何从(2-2-1)式求得母函数H(x)的一种形式算法。所谓形式算法说的是假定这些幂级数在作四则运算时，一如有限项的代数式一样。,递推关系,根据(2-2-1)，,或利用递推关系(2-2-1)有,递推关系,上式左端为：,右端

19、第一项为：,右端第二项为：,递推关系,整理得,这两种做法得到的结果是一样的。即：,递推关系,令,如何从母函数得到序列 ？下面介绍一种化为部分分数的算法。,递推关系,由上式可得：,即：,递推关系,因为：,递推关系,例2. 求n位十进制数中出现偶数个5的数的个数。,先从分析n位十进制数出现偶数个5的数的结构入手 是n-1位十进制数，若含有偶数个5，则 取5以外的0，1，2，3，4，6，7，8，9九个数中的一个，若 只有奇数个5，则取 ，使 成为出现偶数个5的十进制数。,递推关系,解法1：,令 位十进制数中出现偶数个5的数的个数， 位十进制数中出现奇数个5的数 的个数。,故有：,也有类似解释。,递推

20、关系,(2-2-2)式中的 表达了含有偶数个5的n位十进制数的两个组成部分。 表达由含有偶数个5的n-1位十进制数 ，令 取5以外的0，1，2，3，4，6，7，8，9九个数中的一个数构成的 项表示当 是含有奇数个5的n-1位十进制数，令 而得 是含偶数个5的n位十进制数。,(2-2-2)是关于序列 和 的连立关系。,递推关系,设序列 的母函数为 ，序列 的母函数为 。,即：,递推关系,承前页：,递推关系,又：,故得关于母函数 和 得连立方程组：,递推关系,递推关系,递推关系,解法二： n-1位的十进制数的全体共 从中去掉含有偶数个5的数，余下的便是n-1位中含有奇数个5的数。故有：,递推关系,

21、令,递推关系,母函数和递推关系应用举例,例6：设有n条封闭的曲线，两两相交于两点，任意三条封闭曲线不相交于一点。求这样的n条曲线把平面分割成几个部分？ 设满足条件的n条封闭 曲线所分割成的域的数目为 ，其中 条封闭曲线 所分割成的域的数目为,母函数和递推关系应用举例,第n条封闭曲线和这些曲线相交于 个点，这 个点把第n条封闭曲线截成 条弧，每条弧把 个域中的每个域一分为二。故新增加的域数为,利用递推关系 得,母函数和递推关系应用举例,设,母函数和递推关系应用举例,另解：利用欧拉公式 点数+域数-边数=2 点数= ， 边数= 点数 域数=,相关练习,NKOJ 1046 NKOJ1052,二分图的

22、最大匹配,相关概念,二分图是这样一种图：图被分成两个顶点集M和N，在同一个集合中的顶点不存在边，只有不在同一集合的顶点之间才存在边， 二分图匹配是指求出一组边，其中顶点分别在两个集合中，并且没有两个边有相同的依附顶点，也就是说一个顶点最多只属于一条边。 最大匹配就是找出这样的最大边数的一组边。,二分图及其最大匹配示意,二分图最大匹配算法（匈牙利算法）,令g=（x,*,y）是一个二分图，其中x=x1,x2.,y=y1,y2,.令m为g中的任意匹配。 1。将x的所有不与m的边关联的顶点表上￥，并称所有的顶点为未扫描的。转到2。 2。如果在上一步没有新的标记加到x的顶点上，则停，否则 ，转3 3。当

23、存在x被标记但未被扫描的顶点时，选择一个被标记但未被扫描的x的顶点，比如xi，用（xi）标 记y 的所有顶点，这些顶点被不属于m且尚未标记的边连到xi。 现在顶点xi 是被扫描的。如果不存在被标记但未被扫描的顶点，转4。 4。如果在步骤3没有新的标记被标记到y的顶点上，则停，否则转5。 5。当存在y被标记但未被扫描的顶点时。选择y的一个被标记但未被扫描的顶点，比如yj， 用（yj）标记x的顶点，这些顶点被属于m且尚未标记的边连到yj。现在，顶点yj是被扫描的。 如果不存在被标记但未被扫描的顶点则转道2。 由于每一个顶点最多被标记一次且由于每一个顶点最多被扫描一次，本匹配算法在有限步内终止。,相

24、关练习,NKOJ 1060 NKOJ 1070,Polya计数原理的相关数学基础,群的概念,(1)群 定义 给定集合G和G上的二元运算 ，满足下列条件称为群。 (a)封闭性：若a,bG,则存在cG,使得ab=c. (b)结合律成立：任意a,b,cG,有(ab)c=a(bc). (c)有单位元：存在eG,任意aG.ae=ea=a. (d)有逆元：任意aG,存在bG, ab=ba=e. b=a. 由于结合律成立，(ab)c=a(bc)可记做abc. 例 证明对于a1,a2,an的乘积，结合律成立. aaa=a (共n个a相乘).,-1,n,群的概念,(2) 简单例子 例 G=1,-1在普通乘法下是

25、群。 例 G=0,1,2,n-1在mod n的加法下是群. 例 二维欧氏空间所有刚体旋转T=Ta构成群。其中Ta = cosa sina -sina cosa TbTa= cosb sinb cosa sina -sinb cosb -sina cosa,群的概念,= cosacosb-sinasinb sinacosb+cosasinb -sinacosb-cosasinb cosacosb-sinasinb = cos(a+b) sin(a+b) =Ta+b -sin(a+b) cos(a+b) 从而有(a)封闭性; (b)结合律成立：(TT)T = T(TT) = TTT ; (c)有单

26、位元： T0 = ; (d)有逆元：Ta =T-a = cosa -sina sina cosa,1 0 0 1,群的概念,前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，所以是无限群。 有限群G的元素个数叫做群的阶,记做|G|。 若群G的任意二元素a,b恒满足ab=ba。责称G为交换群，或Abel群。 设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。,群的概念,基本性质,单位元唯一 e1e2=e2=e1 消去律成立 ab=ac b=c, ba=ca b=c 每个元的逆元唯一 aa =a a = e, ab = ba = e , aa = a

27、b , a = b (d)(ab.c) =c b a . c b a abc = e,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,-1,群的概念,(e) G有限，aG，则存在最小正整数r，使得a = e.且a = a . 证 设|G|=g,则a,a ,a ,a G,由鸽巢原理其中必有相同项。设a =a ,1mlg+1, e=a ,1l-mg，令l-m=r.则有a =a a=e.即a =a .既然有正整数r使得a =e,其中必有最小者，不妨仍设为r. r称为a的阶。易见 H=a,a ,a ,a =e在原有运算下也是一个群。,r,-1,r-1,2,g,g+1,m,l,l-m,r,r

28、-1,r-1,-1,r,2,r-1,r,置换群,置换群是最重要的有限群，所有的有限群都可以用之表示。 置换：1,n到自身的1-1变换。n阶置换。1,n目标集。( ), a1a2an是1,n中元的一个排列。n阶置换共有n!个，同一置换用这样的表示可有n!个表示法。例如 p1=( )=( )，n阶置换又可看作1,n上的一元运算，一元函数。,1 2 n a1 a2 an,1 2 3 4 3 1 2 4,3 1 4 2 2 3 4 1,置换群,置换乘法 P1=( ),P2=( )P1P2=( )( )=( ) 注意：既然先做P1的置换，再做P2的置换就规定了若作为运算符或函数符应是后置的。这与一般习惯的前置不一样。 一般而言，对1,n上的n阶置换，i1,n要写成(i)P1P2，而不是P1P2(i). (i)P有时写成i 在上面例中，132,214,323,441.也可写(1)P1P2=2,(2)P1P2=4,(