组合数学在程序设计竞赛中的应用组合数学在程序设计竞赛中的应用1内容提要内容提要l排列组合和容斥原理排列组合和容斥原理l群论与群论与Polya定理定理 l递推关系递推关系2两个基本原则两个基本原则1、加法原则、加法原则如果完成一件事情有两种方案，而第一个方案有如果完成一件事情有两种方案，而第一个方案有m种种方法，第二个方案有方法，第二个方案有n中方法，则完成该事情共有中方法，则完成该事情共有m+n种种方法。方法。2、乘法原则、乘法原则如果完成一件事情需要两个步骤，第一步有如果完成一件事情需要两个步骤，第一步有m中方法，中方法，第二步又有第二步又有n种方法，则完成该事情共有种方法，则完成该事情共有m*n种方法种方法3排列组合的几个基本结论排列组合的几个基本结论1、相异元素不允许重复的排列数和组合数、相异元素不允许重复的排列数和组合数： n!(n-r)!P(n,r)=C(n,r)= n!(n-r)!r! 2、不尽相异元素的全排列、不尽相异元素的全排列RP(n,n) = n!n1!n2!.nt!4排列组合的几个基本结论排列组合的几个基本结论3、相异元素不允许重复的圆排列、相异元素不允许重复的圆排列CP(n,n)=P(n,n) n4、相异元素允许重复的组合数、相异元素允许重复的组合数 集合描述：设集合描述：设S=e1, e2, en,，从，从S中允许重中允许重复地取出复地取出r个元素，称为个元素，称为r可重组合可重组合RC(,r)=C(n+r-1,r) = (n+r-1)! r!(n-1)! 5排列组合例题排列组合例题例例1：电子锁：电子锁某机要部门安装了电子锁。某机要部门安装了电子锁。M工作人员每工作人员每人发一张磁卡，卡上有开锁的密码特征，为了人发一张磁卡，卡上有开锁的密码特征，为了确保安全，规定至少有确保安全，规定至少有N人同时使用各自的磁人同时使用各自的磁卡才能将锁打开。卡才能将锁打开。现在需要计算一下，电子锁上至少要有多现在需要计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少要有多少特征。少种特征，每个人的磁卡上至少要有多少特征。6排列组合例题排列组合例题先做一个简单的假设：先做一个简单的假设：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人在场至少缺少一种此人所具有的特征人在场至少缺少一种此人所具有的特征而无法打开锁。每张磁卡至少应有而无法打开锁。每张磁卡至少应有C(M-1,N-1)种特征，故种特征，故C(6,3)=20种特征。种特征。所以最终答案是所以最终答案是C(M,N-1)和和C(M-1,N-1)7排列组合例题排列组合例题例2：zju1976 Path On a Grid 求求n*m的方格图形中，从点（的方格图形中，从点（0，0）到点（）到点（n，m）的最短路径数目）的最短路径数目 （0，0）（n，m）Sample Input （给定（给定n，m）5 41 10 0Sample Output (路径数目)12628排列组合例题排列组合例题我们用组合数学的思路来解题。最短路径必定是一条只向右我们用组合数学的思路来解题。最短路径必定是一条只向右上走得路。设向右走一步为上走得路。设向右走一步为x，向上走一步为，向上走一步为y。则每一条路。则每一条路线一定对应由线一定对应由n个个x，m个个y共共m+n个元素组成的排列。个元素组成的排列。以以n=5，m=4为例，为例， 任意一条路线如下图所示，对应的任意一条路线如下图所示，对应的xy序列序列为：为：xyxxxyxyy可见，只要能确定可见，只要能确定9个位置中个位置中4个个y的位置的位置就唯一确定了一条路径。就唯一确定了一条路径。所以，本题答案就是所以，本题答案就是C(n+m,m)9排列组合数的一般计算方法排列组合数的一般计算方法 20!12!8!C(20，12) =怎么计算？设计一个求阶乘的函数？怎么计算？设计一个求阶乘的函数？20！= 2432900012！= 4790016008！ = 40320C(20,12) = 125970显然显然2020！用！用intint表示一定是失败的，而表示一定是失败的，而C(20,12)C(20,12)的结果又完全的结果又完全可以用可以用intint来表示。来表示。回想我们是怎么计算的回想我们是怎么计算的? ? 先约分再计算！先约分再计算！10排列组合数的一般计算方法排列组合数的一般计算方法（一）计算组合数的函数（一）计算组合数的函数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 =1; i-) product = product * (n-m+i)/ (m-i+1); return product; /* 在输出结果是应该注意要以在输出结果是应该注意要以整数形式输出整数形式输出.*/#include #include using namespace std; int mainint n,m;cinnm;coutsetiosflags(ios:fixed)setprecision(0)C2(n,m)endl;return 0;12排列的生成算法排列的生成算法l字典序法字典序法:顾名思义顾名思义, ,这种方法就是将所有这种方法就是将所有n n元排列按元排列按“字典字典顺序顺序”排成队，以排成队，以1212n n为第一个排列，排序规则，为第一个排列，排序规则，即：由一个排列即：由一个排列P(pP(p1 1,p,p2 2p pn n) )直接生成下一个排列直接生成下一个排列的算法可归结为：的算法可归结为：（1 1）求满足）求满足p pk-1k-1ppk k的的k k的最大值，设为的最大值，设为i,i,即即 i=maxk|pi=maxk|pk-1k-1ppk k （2 2）求满足）求满足p pi-1i-1ppk k的的p pk k的最小值，其位置设为的最小值，其位置设为j,j,即即 p pj j=minp=minpk k|p|pi-1i-1p=6)n(n=6)个数字，要求按字典序输出所有从个数字，要求按字典序输出所有从该该n n个数字中取个数字中取6 6个的组合个的组合。Sample Input712345678123581321340Sample Output12345612345712346712356712456713456723456712358131235821123583412351321n14组合的生成算法组合的生成算法Code:#include#include#includeusing 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&k) if(n_case+) coutendl; for (i = 0 ;i lottoi;sort(lotto,lotto+k);memset(used,0,sizeof(used);choosenext(0,0);return 0;15组合的生成算法组合的生成算法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; 16容斥原理容斥原理1、容斥原理、容斥原理 ： |A1+A2+An| =|Ai|- |AiAj| + |AiAjAk|- +(-1)n-1|A1A2An|ni=11 ij n1 ijk n2、逐步淘汰原理、逐步淘汰原理 |A1.A2An|=|S|-|Ai|+|AiAj|- |AiAjAk|+(-1)n|A1A2An|i=1n1 ij n1 ijk n另外容斥原理还有：另外容斥原理还有：Jordan公式和对称原理等。公式和对称原理等。17容斥原理应用容斥原理应用错排问题。错排问题。问题描述问题描述：n n个元素一次给以标号个元素一次给以标号1 1，2 2，n n进进行全排列，求每个元素不在自己原来位置上的排行全排列，求每个元素不在自己原来位置上的排列数列数D Dn n。解解 令令AiAi表示数表示数i i排在第排在第i i个位置上的所有排列，则个位置上的所有排列，则|Ai| = (n-1)!, i = 1,2,n|AiAj| = (n-2)! i,j = 1,2,n;i j|AiAjAk| = (n-3)! i,j,k = 1,2,n;i,j,k两两不相等两两不相等18容斥原理应用容斥原理应用一般地，一般地， |Ai1Ai2Aik| = (n-k)!, k=1,2,n 我们所求的是：我们所求的是：1 1不在第一位，不在第一位，2 2不在第二位，不在第二位，3 3不不在第三位在第三位n n不在第不在第n n位的全排列数位的全排列数. .即：即： Dn=|A1.A2An| 根据逐步淘汰原理得：根据逐步淘汰原理得：Dn = n! C(n,1)(n-1)! +C(n,2)(n-2)!-(-1)nC(n,n)0! = n!(1-1/1!+1/2!-+(-1)n1/n!)19容斥原理应用容斥原理应用例：例：zju1619zju1619PresentPresent n n个朋友每人买了一份礼物，混合在一起后，每个朋友每人买了一份礼物，混合在一起后，每人拿一份，求恰有人拿一份，求恰有m m人拿到了恰好是自己买的礼人拿到了恰好是自己买的礼物的概率。物的概率。即即:n:n个数的全排列中，个数的全排列中，m m个保位个保位,(n-m),(n-m)个错位的排个错位的排列数占总排列数的比例。列数占总排列数的比例。全排列数：全排列数：n!n!m m个保位个保位,(n-m),(n-m)错位的排列数：错位的排列数：C(n,m)DC(n,m)Dn-mn-m结论：结论：p = C(n,m)Dp = C(n,m)Dn-mn-m/n!/n!20容斥原理应用容斥原理应用#include#includeusing namespace std;double jc100; void JC()jc0 = 1.0;int i;for(i = 1; i nm) double res = 0; int i; for(i = 0 ;i = n-m; i+) if(i%2=0) res+=jci;else res-=jci; res*=jcm; coutsetiosflags(ios:fixed)setprecision(8 )resendl; return 0;22群论群论 群：群：给定非空集合给定非空集合G G及定义在及定义在G G上的二元运算上的二元运算“. .”，若满足以下四个条件，则称集合，若满足以下四个条件，则称集合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的的 逆元素，记为逆元素，记为a-1;23群论群论置换：置换：n个元素个元素1,2,n之间的一个置换：之间的一个置换：1 2 na1 a2 an 表示表示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 42 4 3 124群论群论循环 记：(a1a2an)=a1 a2 an-1 ana2 a3 an a1称为：称为：n n阶循环。每个置换都可以写成若干个互不相交的阶循环。每个置换都可以写成若干个互不相交的循环的乘积，两个循环循环的乘积，两个循环(a(a1 1a a2 2a an n) )和和(b(b1 1b b2 2b bn n) )互不相交互不相交是指是指a ai i b bj j, i,j = 1,2, i,j = 1,2,n.n.例如：例如：1 2 3 4 5 63 5 6 4 2 1= (1 3 6)(2 5)(4)循环又叫循环又叫轮换轮换，二阶轮换叫，二阶轮换叫对换对换25群论群论轮换上乘上一个对换的效果：(1)(1)、对换的两个元素分属于不同、对换的两个元素分属于不同 的轮换中的轮换中两个轮换合并两个轮换合并 成一个轮换。成一个轮换。有连个轮换有连个轮换( (a a1 1,a,a2 2,a,a3 3, ,a an n),(b),(b1 1,b,b2 2,b,b3 3,b,bn n),),一个对换一个对换(a(a1 1,b,b1 1) )( (a a1 1,a,a2 2,a,a3 3, ,a an n) (a) (a1 1,b,b1 1)(b)(b1 1,b,b2 2,b,b3 3,b,bn n)=(a)=(a1 1,a,a2 2, ,b,b1 1,b,b2 2b bn n) )(2)(2)、对换的两个元素属于同一个轮换、对换的两个元素属于同一个轮换一个轮换拆分成了一个轮换拆分成了 两个轮换两个轮换(a1,a2,a3,an)(a1,ai) = (a1,a2,ai-1)(ai,ai+1,an)26群论群论例：传球游戏例：传球游戏 两个组进行传球比赛。每组两个组进行传球比赛。每组n n人，围成一个圈，每人有一人，围成一个圈，每人有一个个在该组中唯一的编号（在该组中唯一的编号（1 1n n之间），每人有一个编号（之间），每人有一个编号（1 1n n）在该组唯一的球。每个人的球的编号是任意给定的。然后，游在该组唯一的球。每个人的球的编号是任意给定的。然后，游戏开始，每组的人开始进行组内对传，争取以最短的时间把球戏开始，每组的人开始进行组内对传，争取以最短的时间把球传到位。传到位是指一个组中的每个人手中的球的编号与他自传到位。传到位是指一个组中的每个人手中的球的编号与他自己的编号相同。最后获胜的就是那个用最少的传球次数把球己的编号相同。最后获胜的就是那个用最少的传球次数把球传到位的组。传到位的组。现需要你编一个程序从初始状态确定至少需几次对传才能将球现需要你编一个程序从初始状态确定至少需几次对传才能将球传到位。传到位。27群论群论分析：分析：初始状态为一个置换，假设为：初始状态为一个置换，假设为：1 2 3 4 5 6 3 5 6 4 2 1末状态为末状态为n n个长度为个长度为1 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)(2 5)(1 3)(1 6)28群论群论结论结论: : 1 1、把初始状态转化成一系列轮换之积、把初始状态转化成一系列轮换之积2 2、若原轮换的长度为、若原轮换的长度为n n，次数为，次数为n-1n-1；29Polya定理定理例：手镯例：手镯pku1286pku1286如果手镯有如果手镯有n n个位置可用来嵌入宝石，有个位置可用来嵌入宝石，有m m种宝种宝石可以嵌入，能生产出多少种不同类的手镯？石可以嵌入，能生产出多少种不同类的手镯？如果将其中一只手镯做某种旋转或翻转使得两如果将其中一只手镯做某种旋转或翻转使得两个手镯完全一样，我们认为这两个手镯是同类的。个手镯完全一样，我们认为这两个手镯是同类的。翻转翻转旋转旋转30Polya定理定理对于有对于有4 4个嵌宝个嵌宝石位置的手镯石位置的手镯来说，有来说，有4 4种旋种旋转方式，有转方式，有4 4种种翻转方式，用翻转方式，用轮换相乘来表轮换相乘来表示：示：1234置换置换轮换相乘轮换相乘C(i)C(i)循环节数循环节数旋转旋转1 1(1)(2)(3)(4)4旋转旋转2 2(1 2 3 4)1旋转旋转3 3(1 3)(2 4)2旋转旋转4 4(1 4 3 2)1翻转翻转1 1(1 4)(2 3)2翻转翻转2 2(1)(3)(2 4)3翻转翻转3 3(1 2)(3 4)2翻转翻转4 4(2)(4)(1 3)331Polya定理定理PolyaPolya定理定理： 设设G G是是p p个对象的一个置换群，用个对象的一个置换群，用k k种颜色涂染这种颜色涂染这p p个对个对象，若一种染色方案在群象，若一种染色方案在群G G的作用下变为另一种方案，则这的作用下变为另一种方案，则这两个方案当作是同一种方案，这样的不同染色方案数为：两个方案当作是同一种方案，这样的不同染色方案数为：L = 1 G f Gkc(f)对于手镯一题，设对于手镯一题，设n=4,m=2n=4,m=2L = (2L = (24 4+2+2+2+22 2+2+2+2+22 2+2+23 3+2+22 2+2+23 3)/8=6)/8=6|G| -置换群的元素是置换置换群的元素是置换c(f)-循环节数循环节数32Polya定理定理置换及循环节数的计算方法置换及循环节数的计算方法: :对于有对于有n n个位置的手镯，有个位置的手镯，有n n种旋转置换和种旋转置换和n n种翻转置换种翻转置换对于旋转置换对于旋转置换: c(fi) = gcd(n,i) i: c(fi) = gcd(n,i) i为一次转过为一次转过i i颗宝石。颗宝石。 i = 0 i = 0 时时 c=n;c=n; 对于翻转置换对于翻转置换: :如果如果n n为偶数为偶数 c(f) = n/2 c(f) = n/2 的置换有的置换有n/2n/2个个; ; c(f) = n/2+1 c(f) = n/2+1 的置换有的置换有n/2n/2个个如果如果n n为奇数，为奇数，c(f) = n/2+1;c(f) = n/2+1;33Polya定理定理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 & n!=-1) if(n=0) cout0endl; else coutsetiosflags(ios:fixed) setprecision(0)go(n)endl; return 0; 34Polya定理定理double go(int n) double r=0; int i; for(i=0;in;i+) if(i=0) r+=pow(4.0,n); else r+=pow(4.0,gcd(n,i); if(n%2=0) r+=n/2*(pow(4.0,n/2+1)+pow(4.0,n/2); else r+=n*(pow(4.0,n/2+1); return r/n/2;35递推关系递推关系 在一些计数问题中，很难直接得到计数在一些计数问题中，很难直接得到计数序列序列aiai的通项公式，但是可以建立相邻几项的的通项公式，但是可以建立相邻几项的关系，可以利用这些关系一步步计算出需要的值，关系，可以利用这些关系一步步计算出需要的值，或者求解递推关系得到通项公式。或者求解递推关系得到通项公式。例例1 1上楼梯问题上楼梯问题 某人欲登上某人欲登上n n级楼梯，若每次只能跨一级或级楼梯，若每次只能跨一级或 两级，问他从地面上到第两级，问他从地面上到第n n级楼梯，共有多少种不同的方法。级楼梯，共有多少种不同的方法。解，假设上到第解，假设上到第n n级楼梯的方法数为级楼梯的方法数为a an n，那么，第一步无非有，那么，第一步无非有两种走法：两种走法：（1 1）跨一级，则余下的）跨一级，则余下的n-1n-1级有级有a an-1n-1种上法；种上法；（2 2）跨两级，则余下的）跨两级，则余下的n-2n-2级有级有a an-2n-2种上法；种上法；所以所以 a an n = a = an-1n-1 + a + an-2n-2; ;36递推关系递推关系例zju1475 ranklistn个人参加比赛，有多少种不同的名次排列方法，注意多人并列的情况。Sample InputSample Input123-1Sample OutputSample Output1313n输入输入结束结束37递推关系递推关系分析：分析：设设n n个人参加比赛，个人参加比赛，m m个不同名次的个不同名次的ranklistranklist共共有有F(n,m)F(n,m)个，则：个，则：F(n,m)=F(n,m)=( (在在n-1n-1个人个人m-1m-1个不同名次的个不同名次的ranklistranklist中增加一个名次共有中增加一个名次共有m m种方法种方法) )mF(n-1,m-1)mF(n-1,m-1)mF(n-1,m)mF(n-1,m)( (将新增加的一人加到将新增加的一人加到m m个名次中个名次中的任一个中有的任一个中有m m种方法种方法) )结论：结论：An = F(n,1)+F(n,2)+An = F(n,1)+F(n,2)+F(n,n)+F(n,n)+ +38