组合数学竞赛中的应用

《组合数学竞赛中的应用》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

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!n1!n2!...nt!排列组合的几个基本结论3、相异元素不允许重复的圆排列CP(n,n)=P(n,n)n4、

2、相异元素允许重复的组合数集合描述：设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。对于问题一：任意N-1人在一起，至少缺一种特征，不能打开,剩下的M-(N-1)个人中的任意一个到场即可开锁。M个人中的M-(

3、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)排列组合例题例2：zju1976PathOnaGrid求n*m的方格图形中，从点（0，0）到点（n，m）的最短路径数目（0，0）（n，m）SampleInput（给定n，m）541100SampleOutput(路径数目)1262排列组合例题我们用组合数学的

4、思路来解题。最短路径必定是一条只向右上走得路。设向右走一步为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)的结果又完全可以用i

5、nt来表示。回想我们是怎么计算的?先约分再计算！排列组合数的一般计算方法（一）计算组合数的函数intgcd(inta,intb){if(b==0)returna;elsereturngcd(b,a%b);}//欧几里德辗转相除法求最大公约数gcd(a,b)=gcd(b,amodb)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){do

6、ubleproduct=1;inti;for(i=m;i>=1;i--){product=product*(n-m+i)/(m-i+1);}returnproduct;}/*在输出结果是应该注意要以整数形式输出.*/#include#includeusingnamespacestd;intmain{intn,m;cin>>n>>m;cout<

7、2……n为第一个排列，排序规则，即：由一个排列P(p1,p2……pn)直接生成下一个排列的算法可归结为：（1）求满足pk-1

8、pk-1

9、pi-1