13 组合数学竞赛中的应用

1、组合数学在程序设计竞赛中的应用,内容提要,排列组合和容斥原理,群论与,Polya,定理,递推关系,两个基本原则,1,加法原则,如果完成一件事情有两种方案，而第一个方案有,m,种,方法，第二个方案有,n,中方法，则完成该事情共有,m+n,种,方法,2,乘法原则,如果完成一件事情需要两个步骤，第一步有,m,中方法,第二步又有,n,种方法，则完成该事情共有,m*n,种方法,排列组合的几个基本结论,1,相异元素不允许重复的排列数和组合数,n,n-r),P(n,r),C(n,r),n,n-r)!r,2,不尽相异元素的全排列,RP(n,n),n,n,1,n,2,n,t,排列组合例题,例,1,电子锁,某机要

2、部门安装了电子锁,M,工作人员每,人发一张磁卡，卡上有开锁的密码特征，为了,确保安全，规定至少有,N,人同时使用各自的磁,卡才能将锁打开,现在需要计算一下，电子锁上至少要有多,少种特征，每个人的磁卡上至少要有多少特征,排列组合例题,先做一个简单的假设,M=7,N=4,对于问题一：任意,N-1,人在一起，至少缺一种特征,不能打开,剩下的,M-(N-1,个人中的任意一个到场即可开锁,M,个人中的,M-(N-1,的组合数为,C(M,M-N+1)=C(M,N-1,故,电子锁的至少应有,C(7,3)=35,种特征,对于问题二：对任一位工作者的磁卡而言，其,余,M-1,人中任意,N-1,人在场至少缺少一种

3、此人所具有的特征,而无法打开锁。每张磁卡至少应有,C(M-1,N-1,种特征，故,C(6,3)=20,种特征,所以最终答案是,C(M,N-1,和,C(M-1,N-1,排列组合例题,例,2,zju1976 Path On a Grid,求,n*m,的方格图形中，从点,0,0,到点,n,m,的最短路径数目,0,0,n,m,Sample Input,给定,n,m,5 4,1 1,0 0,Sample Output,路径数目,126,2,排列组合例题,我们用组合数学的思路来解题。最短路径必定是一条只向右,上走得路。设向右走一步为,x,向上走一步为,y,则每一条路,线一定对应由,n,个,x,m,个,y,

4、共,m+n,个元素组成的排列,以,n=5,m=4,为例,任意一条路线如下图所示，对应的,xy,序列,为,xyxxxyxyy,可见，只要能确定,9,个位置中,4,个,y,的位置,就唯一确定了一条路径,所以，本题答案就是,C(n+m,m,排列组合数的一般计算方法,20,12!8,C(20,12),怎么计算？设计一个求阶乘的函数,20,2432902008176640000,12,479001600,8,40320,C(20,12),125970,显然,20,用,int,表示一定是失败的，而,C(20,12,的结果又完全,可以用,int,来表示,回想我们是怎么计算的,先约分再计算,排列组合数的一般计

5、算方法,一）计算组合数的函数,int gcd(int a, int b,if(b=0)return a,else return gcd(b,a%b,欧几里德辗转相除法求最大公,约数,gcd(a,b) = gcd(b,a mod 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,fm,fz/=a,fm/=a,return fz/fm,分子,分母,排列组合数的一般计算方法,二）使用,double,类型,double C2(int n , int m,double produ

6、ct=1; int i,for(i=m; i=1; i,product = product * (n-m+i)/ (m-i+1,return product,在输出结果是应该注意要以,整数形式输出,include,include,using namespace std,int main,int n,m,cinnm,coutsetiosflags(ios:fixed,setprecision(0)C2(n,m)endl,return 0,排列的生成算法,字典序法,顾名思义,这种方法就是将所有,n,元排列按“字典,顺序”排成队，以,12,n,为第一个排列，排序规则,即：由一个排列,P(p,1,p,

7、2,p,n,直接生成下一个排列的,算法可归结为,1,求满足,p,k-1,p,k,的,k,的最大值，设为,i,即,i=maxk|p,k-1,p,k,2,求满足,p,i-1,p,k,的,p,k,的最小值，其位置设为,j,即,p,j,minp,k,p,i-1,p,k,3,p,i-1,与,p,j,互换位置得,q,q,1,q,2,q,n,4,q),q,1,q,2,q,i-1,q,i,q,i+1,q,n,中,q,i,q,i+1,q,n,部分的顺,序逆转，得,q,1,q,2,q,i-1,q,n,q,i+1,q,i,这便是下一个排列,如排列,839647521,首先从最右端开始，找,到第一个比它的右临位小的数

8、字，即,4,然后,从该数字的右边找到比它大的最小的数字,即,5,交换两数字，原排列变为,839657421,最,后将,5,位置右端的数字倒序排列，即变为,839651247,这就是原排列的下一排列,组合的生成算法,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

9、5 6 7,1 2 3 5 8 13,1 2 3 5 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(cinki k ;i,cinlottoi,sort(lotto,lotto+k,memset(used,0,sizeof(used,choosene

10、xt(0,0,return 0,组合的生成算法,void output(,int i,n=0,for(i = 0 ;i k ; i,if(usedi,if(n) cout,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,容斥原理,1,容斥原理,A,1,A,2,A,n,A,i,A,i,A,j,A,i,A,j,A,k,(-1

11、,n-1,A,1,A,2,A,n,n,i=1,1,ij,n,1,ijk,n,2,逐步淘汰原理,A,1,A,2,A,n,S,A,i,A,i,A,j,A,i,A,j,A,k,(-1,n,A,1,A,2,A,n,i=1,n,1,ij,n,1,ijk,n,另外容斥原理还有,Jordan,公式和对称原理等,容斥原理应用,错排问题,问题描述,n,个元素一次给以标号,1,2,n,进,行全排列，求每个元素不在自己原来位置上的排,列数,D,n,解,令,Ai,表示数,i,排在第,i,个位置上的所有排列，则,Ai| = (n,1)!, i = 1,2,n,AiAj| = (n,2)! i,j = 1,2,n;i,j

12、,AiAjAk| = (n,3)! i,j,k = 1,2,n;i,j,k,两两不相等,容斥原理应用,一般地,A,i1,A,i2,A,ik, = (n,k)!, k=1,2,n,我们所求的是,1,不在第一位,2,不在第二位,3,不,在第三位,n,不在第,n,位的全排列数,即,Dn=|A1,A2An,根据逐步淘汰原理得,Dn = n,C(n,1)(n-1)! +C(n,2)(n-2),1,n,C(n,n)0,n!(1-1/1!+1/2,1,n,1/n,容斥原理应用,例,zju1619,Present,n,个朋友每人买了一份礼物，混合在一起后，每,人拿一份，求恰有,m,人拿到了恰好是自己买的礼,物

13、的概率,即,n,个数的全排列中,m,个保位,n-m,个错位的排,列数占总排列数的比例,全排列数,n,m,个保位,n-m,错位的排列数,C(n,m)D,n-m,结论,p = C(n,m)D,n-m,n,容斥原理应用,include,include,using namespace std,double jc100,void JC(,jc0 = 1.0,int i,for(i = 1; i 100; i,jci = jci-1/(double)i,容斥原理应用,int main(,int m,n,curr=1,JC(,while(cinnm,double res = 0; int i,for(i =

14、 0 ;i = n-m; i+),if(i%2=0) res+=jci,else res-=jci,res*=jcm,coutsetiosflags(ios:fixed)setprecision(8 )resendl,return 0,群论,群,给定非空集合,G,及定义在,G,上的二元运算,若,满足以下四个条件，则称集合,G,在运算,下构成一个群,简称,G,群,1,封闭性,a,b,G,则,a,b,G,2,结合律,a,b,c=a,b,c,3,单位元：存在,e,G,对任意,a,G,有,a,e=e.a=a,4,逆元素：对任意,a,G,存在,b,G,使得,a,b=b,a=e,称,b,为,a,的,逆元素

15、，记为,a,1,群论,置换,n,个元素,1,2,n,之间的一个置换,1 2 n,a,1,a,2,a,n,表示,1,被,1,到,n,中的某个数,a1,取代,2,被,1,到,n,中的某个数,a2,取代,直到,n,被,1,到,n,中的某个数,an,取代，且,a1,a2an,互不,相同,置换群,置换群的元素是置换,运算是置换的连接,例如,1 2 3 4 1 2 3 4,3 1 2 4 4 3 2 1,1 2 3 4,2 4 3 1,群论,循环,记,a,1,a,2,a,n,a,1,a,2,a,n-1,a,n,a,2,a,3,a,n,a,1,称为,n,阶循环。每个置换都可以写成若干个互不相交的,循环的乘积

16、，两个循环,a,1,a,2,a,n,和,b,1,b,2,b,n,互不相交,是指,a,i,b,j,i,j = 1,2,n,例如,1 2 3 4 5 6,3 5 6 4 2 1,(1 3 6)(2 5)(4,循环又叫,轮换,二阶轮换叫,对换,群论,轮换上乘上一个对换,的效果,1,对换的两个元素分属于不同,的轮换中,两个轮换合并,成一个轮换,有连个轮换,a,1,a,2,a,3,a,n,(b,1,b,2,b,3,b,n,一个对换,a,1,b,1,a,1,a,2,a,3,a,n,(a,1,b,1,(b,1,b,2,b,3,b,n,(a,1,a,2,b,1,b,2,b,n,2,对换的两个元素属于同一个轮换

17、,一个轮换拆分成了,两个轮换,a,1,a,2,a,3,a,n,(a,1,a,i,= (a,1,a,2,a,i-1,(a,i,a,i+1,a,n,群论,例：传球游戏,两个组进行传球比赛。每组,n,人，围成一个圈，每人有一个,在该组中唯一的编号,1,n,之间），每人有一个编号,1,n,在该组唯一的球。每个人的球的编号是任意给定的。然后，游,戏开始，每组的人开始进行组内对传，争取以最短的时间把球,传到位。传到位是指一个组中的每个人手中的球的编号与他自,己的编号相同。最后获胜的就是那个用最少的传球次数把球,传到位的组,现需要你编一个程序从初始状态确定至少需几次对传才能将球,传到位,群论,分析,初始状态

18、为一个置换，假设为,1 2 3 4 5 6,3 5 6 4 2 1,末状态为,n,个长度为,1,的轮换,1)(2)(3)(4)(5)(6,1 2 3 4 5 6,3 5 6 4 3 2,(1 3 6)(2 5)(4,乘以,2 5,1 3 6)(2)(5)(4,乘以,1 3,1 6)(3)(2)(5)(4,乘以,1 6,所以：在该假设下，至少需要,次对换，分别是,2 5)(1 3)(1 6,群论,结论,1,把初始状态转化成一系列轮换之积,2,若原轮换的长度为,n,次数为,n-1,Polya,定理,例：手镯,pku1286,如果手镯有,n,个位置可用来嵌入宝石，有,m,种宝,石可以嵌入，能生产出多

19、少种不同类的手镯,如果将其中一只手镯做某种旋转或翻转使得两,个手镯完全一样，我们认为这两个手镯是同类的,翻转,旋转,Polya,定理,对于有,4,个嵌宝,石位置的手镯,来说，有,4,种旋,转方式，有,4,种,翻转方式，用,轮换相乘来表,示,1,2,3,4,置换,轮换相乘,C(i,循环节数,旋转,1,1)(2)(3)(4,4,旋转,2,1 2 3 4,1,旋转,3,1 3)(2 4,2,旋转,4,1 4 3 2,1,翻转,1,1 4)(2 3,2,翻转,2,1)(3)(2 4,3,翻转,3,1 2)(3 4,2,翻转,4,2)(4)(1 3,3,Polya,定理,Polya,定理,设,G,是,p

20、,个对象的一个置换群，用,k,种颜色涂染这,p,个对象,若一种染色方案在群,G,的作用下变为另一种方案，则这两个,方案当作是同一种方案，这样的不同染色方案数为,L,1,G,f,G,k,c(f,对于手镯一题，设,n=4,m=2,L = (2,4,2+2,2,2+2,2,2,3,2,2,2,3,8=6,G,置换群的元素是置换,c(f),循环节数,Polya,定理,置换及循环节数的计算方法,对于有,n,个位置的手镯，有,n,种旋转置换和,n,种翻转置换,对于旋转置换,c(fi) = gcd(n,i) i,为一次转过,i,颗宝石,i = 0,时,c=n,对于翻转置换,如果,n,为偶数,c(f) = n/2,的置换有,n/2,个,c(f) = n/2+1,的置换有,n/2,个,如果,n,为奇数,c(f) = n/2+1,Polya,定理,Code,include,include,include,using namespace std,int gcd(int a,int b,return b?gcd(b,a%b):a,double go(int n,int main(,int n,while(cinn int