13-组合数学竞赛中应用.ppt

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个对象的一个置换群，用k种颜色涂染这p个对象，若一种染色方案在群G的作用下变为另一种方案，则这两个方案当作是同一种方案，这样的不同染色方案数为： L = 1 G ∑ f∈ G kc(f) 对于手镯一题，设n=4,m=2 L = (24+2+22+2+22+23+22+23)/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 iostream #include cmath #include iomanip 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; } Polya定理 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; } 递推关系 在一些计数问题中，很难直接得到计数序列[ai]的通项公式，但是可以建立相邻几项的关系，可以利用这些关系一步步计算出需要的值，或者求解递推关系得到通项公式。 例1上楼梯问题 某人欲登上n级楼梯，若每次只能跨一级或 两级，问他从地面上到第n级楼梯，共有多少种不同的方法。 解，假设上到第n级楼梯的方法数为an，那么，第一步无非有 两种走法： （1）跨一级，则余下的n-1级有an-1种上法； （2）跨两级，则余下的n-2级有an-2种上法； 所以 an = an-1 + an-2; 递推关系 例zju1475 ranklist n个人参加比赛，有多少种不同的名次排列方法， 注意多人并列的情况。 Sample Input 123-1  Sample Output 1313 n 输入结束 递推关系 分析： 设n个人参加比赛，m个不同名次的ranklist共有F(n,m)个，则： F(n,m)= (在n-1个人m-1个不同名次的ranklist 中增加一个名次共有m种方法) mF(n-1,m-1) mF(n-1,m) (将新增加的一人加到m个名次中 的任一个中有m种方法) 结论：An = F(n,1)+F(n,2)+…+F(n,n) + 组合数学在程序设计竞赛中的应用 内容提要 排列组合和容斥原理 群论与Polya定理 递推关系 两个基本原则 1、加法原则 如果完成一件事情有两种方案，而第一个方案有m种方法，第二个方案有n中方法，则完成该事情共有m+n种方法。 2、乘法原则 如果完成一件事情需要两个步骤，第一步有m中方法，第二步又有n种方法，则完成该事情共有m*n种方法 排列组合的几个基本结论 1、相异元素不允许重复的排列数和组合数：