组合数学在程序设计竞赛中的应用

组合数学在程序设计竞赛中的应用（一）软件学院2003级穆浩英内容提要排列组合和容斥原理群论与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!n1!n2!...nt!排列组合的几个基本结论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)!排列组合例题例1：电子锁某机要部门安装了电子锁。M工作人员每人发一张磁卡，卡上有开锁的密码特征，为了确保安全，规定至少有N人同时使用各自的磁卡才能将锁打开。现在需要计算一下，电子锁上至少要有多少种特征，每个人的磁卡上至少要有多少特征。排列组合例题先做一个简单的假设：M=7，N=4。对于问题一：任意3人在一起，至少缺一种特征，不能打开。电子锁的至少应有C(7,3)=35种特征。对于问题二：对任一位工作者的磁卡而言，其余6人中任意3人在场至少缺少一种A所具有的特征而无法打开大门。每张磁卡至少应有C(6,3)=20种特征所以总终答案是C(M,N-1)和C(M-1,N-1)排列组合例题例2：zju1976PathOnaGrid求n*m的方格图形中，从点（0，0）到点（n，m）的最短路径数目（0，0）（n，m）SampleInput（给定n，m）541100SampleOutput(路径数目)1262排列组合例题我们用组合数学的思路来解题。最短路径必定是一条只向右上走得路。设向右走一步为x，向上走一步为y。则每一条路线一定对应由n个x，m个y共m+n个元素组成的排列。以n=5，m=4为例，任意一条路线如下图所示，对应的xy序列为：xyxxxyxyy可见，只要能确定9个位置中4个y的位置就唯一确定了一条路径。所以，本题答案就是C(n+m,m)排列组合数的一般计算方法20!12!8!C(20，12)=怎么计算？设计一个求阶乘的函数？20！=243290200817664000012！=4790016008！=40320C(20,12)=125970显然20！用int表示一定是失败的，而C(20,12)的结果又完全可以用int来表示。回想我们是怎么计算的?先约分再计算！排列组合数的一般计算方法（一）计算组合数的函数intgcd(inta,intb){if(b==0)returna;elsereturngcd(b,a%b);}//欧几里德辗转相除法求最大公约数intC(intn,intm){inti,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;}returnfz/fm;}分子分母排列组合数的一般计算方法（二）使用double类型doubleC2(intn,intm){doubleproduct;inti;for(i=m;i=1;i--){product=product/i*(n+i);}returnproduct;}/*在输出结果是应该注意要以整数形式输出.*/#includeiostream#includeiomanipusingnamespacestd;intmain{intn,m;cinnm;coutsetiosflags(ios::fixed)setprecision(0)C2(n,m)endl;return0;}排列的生成算法字典序法:顾名思义,这种方法就是将所有n元排列按“字典顺序”排成队，以12……n为第一个排列，排序规则，即：由一个排列P(p1,p2……pn)直接生成下一个排列的算法可归结为：（1）求满足pk-1pk的k的最大值，设为i,即i=max{k|pk-1pk}（2）求满足pi-1pk的k的最大值，设为j,即j=max{k|pi-1pk}（3）pi-1与pj互换位置得（q）=（q1q2……qn）（4）(q)=（q1q2……qi-1qiqi+1……qn）中qiqi+1……qn部分的顺序逆转，得q1q2……qi-1qqn……qi+1qi这便是下一个排列.组合的生成算法Zju1089有n(n=6)个数字，要求按字典序输出所有从该n个数字中取6个的组合。SampleInput712345678123581321340SampleOutput12345612345712346712356712456713456723456712358131235821123583412351321……n组合的生成算法Code:#includeiostream#includememory#includealgorithmusingnamespacestd;intk;intused[13];intlotto[13];voidoutput();voidchoosenext(intI,intnum);intmain(){intn_case=0,i;while(cink&&k){if(n_case++)coutendl;for(i=0;ik;i++)cinlotto[i];sort(lotto,lotto+k);memset(used,0,sizeof(used));choosenext(0,0);}return0;}组合的生成算法voidoutput(){inti,n=0;for(i=0;ik;i++){if(used[i]){if(n)cout'';coutlotto[i];n++;}}coutendl;}voidchoosenext(intI,intnum){if(num==6){output();return;}if(I==k)return;for(inti=I;ik;i++){used[i]=1;choosenext(i+1,num+1);used[i]=0;}}容斥原理1、容斥原理：|A1+A2+……+An|=∑|Ai|-∑|AiAj|+∑|AiAjAk|-…+(-1)n-1|A1A2…An|ni=11≤ij≤n1≤ijk≤n2、逐步淘汰原理|A1.A2…An|=|S|-∑|Ai|+∑|AiAj|-∑|AiAjAk|+…+(-1)n|A1A2…An|i=1n1≤ij≤n1≤ijk≤n另外容斥原理还有：Jordan公式和对称原理、对称筛。容斥原理应用1、错排问题。问题描述：n个元素一次给以标号1，2，…，n进行全排列，求每个元素不再自己原来位置上的排列数Dn。解令Ai表示数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两两不相等容斥原理应用一般地，|Ai1Ai2…Aik|=(n-k)!,k=1,2…,n我们所求的是：1不在第一位，2不在第二位，3不在第三位……n不在第n位的全排列数.即：Dn=|A1.A2…An|根据逐步淘汰原理得：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!)容斥原理应用例：zju1619Presentn个朋友每人买了一份礼物，混合在一起后，每人拿一份，求恰有m人拿到了恰好是自己买的礼物的概率。即:n个数的全排列中，m个保位,(n-m)个错位的排列数占总排列数的比例。全排列数：n!m个保位,(n-m)错位的排列数：C(n,m)Dn-m结论：p=C(n,m)Dn-m/n!容斥原理应用#includeiostream#includeiomanipusingnamespacestd;doublejc[100];voidJC(){jc[0]=1.0;inti;for(i=1;i100;i++){jc[i]=jc[i-1]/(double)i;}}容斥原理应用intmain(){intm,n,curr=1;JC();while(cinnm){doubleres=0;inti;for(i=0;i=n-m;i++){if(i%2==0)res+=jc[i];elseres-=jc[i];}res*=jc[m];coutsetiosflags(ios::fixed)setprecision(8)resendl;}return0;}群论群：给定非空集合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;群论置换：n个元素1,2,…,n之间的一个置换：12…na1a2…an表示被1到n中的某个数a1取代，2被1到n中的某个数a取代，直到n被1中的某个数an取代，且a1,a2…an互不相同。置换群:置换群的元素是置换，运算是置换的连接。例如：1234123431244321=12342431群论循环记：(a1a2…an)=a1a2…an-1ana2a3…ana1称为：n阶循环。每个置换都可以写成若干个互不相交的循环的乘积，两个循环(a1a2…an)和(b1b2…bn)互不相交是指ai≠bj,i,j=1,2,…n.例如：123456356421=(136)(25)(4)循环又叫轮换，二阶轮换叫对换群论轮换上乘上一个对换的效果：(1)、对换的两个元素分属于不同的轮换中——两个轮换合并成一个轮换。有连个轮换(a1,a2,a3,…an),(b1,b2,b3…,bn),一个对换(a1,b1)(a1,a2,a3,…an)(a1,b1)(b1,b2,b3…,bn)=(a1,a2,…,b1,b2…bn)(2)、对换的两个元素属于同一个轮换——一个轮换拆分成了两个轮换(a1,a2,a3,…,an)(a1,ai)=(a1,a2,…ai-1)(ai,ai+1,…,an)群论例：传球游戏两个组进行传球比赛。每组n人，围成一个圈，每人有一个在该组中唯一的编号（1…n之间），每人有一个编号（1…n）在改组唯一的球。每个人的球的编号是任意给定的。然后，游戏开始，每组的人开始进行组内对传，争取以最短的时间把球传到位。传到位是指一个组中的每每人手中的球的编号与他自己的编号相同。最后获胜的就是那个用最少的地传球次数把球传到位的组。现需要你编一个程序从初始状态确定至少需几次对传才能将球传到位。群论分析：初始状态为一个置换，假设为：123456356432末状态为n个长度为1的轮换：(1)(2)(3)(4)(5)(6)123456356432=(136)(25)(4)乘以(25)(136)(2)(5)(4)乘以(13)(16)(3)(2)(5)(4)乘以(16)所以：在该假设下，至少需要３次对换，分别是(25)(13)(16)群论结论:1、把初始状态转化成一系列轮换之积2、若原轮换的长度为n，次数为n-1；Polya定理例：手镯pku1286如果手镯有n个位置可用来嵌入宝石，有m种宝石可以嵌入，能生产出多少种不同类的手镯？如果将其中一只手镯做某种旋转或翻转使得两个手镯完全一样，我们认为这两个手镯是同类的。翻转旋转Polya定理对于有4个嵌宝石位置的手镯来说，有4种旋转方式，有4种翻转方式