ACM组合数学知识

1、ACM组合数学知识,我的一些总结,目录,基本组合计数 容斥原理 置换群 Polya定理,基本组合计数,加法原理 设事件A有m种选取方式，事件B有n种选取方式，则选A或B共有m+n种选取方式. 乘法原理 设事件A有m种选取方式，事件B有n种选取方式，那么选取A以后再选取B共有m*n种方式.,基本组合计数,排列问题 n个不同物品中选取r个进行排列的方案数。 记 组合问题 n个不同物品中选取r个的方案数。 记,组合数恒等式,组合数的计算,预处理组合数 O(n2) 预处理排列 O(n) 直接求 O(m),大组合数取模(*),n,m为大数,p=105,p为质数,Lucas定理,C(n,m)%p的值等于将

2、n,m化为p进制数后，各对应数对的组合数的连乘积%p。,Lucas定理,大组合数取模(*),问题转化为：,排列数的计算,预处理排列 O(n) Stirling逼近(见附件),正整数的分拆,粗略的说，正整数的分拆就是将一个正整数分成几个正整数的和。 n = n1 + n2 + + nk (k 1, ni 0, 1 i k) 是正整数n的一个k分拆. 分拆分为有序和无序 有序: 3 = 2 + 1 与 3 = 1 + 2 是不一样的 无序: 则一样,正整数的有序分拆,正整数n的有序k分拆的个数为 跟多重集合组合相似，只是每个元素至少出现一次,正整数的无序分拆,我们用B(n, k)来表示n的k分拆的

3、个数，用B(n)表示n的所有分拆的个数，则显然有 (1) B(n, k) = 0 (k n); (2) B(n) = 定理: B(n+k, k) = B(n, 1) + B(n, 2) + + B(n, k) 及 B(n, 1) = B(n, n) = 1; 同样这定理也很容易证明(可用Ferrers图证明),Ferrers图像,图像概念 一个从上而下的n层格子，mi 为第i层的格子数，当mi=mi+1(i=1,2,n-1) ，即上层的格子数不少于下层的格子数时，称之为Ferrers图像。 图像性质 （1）每一层至少有一个格子； （2）第一行与第一列互换，第二行与第二列互换，所得到的图象仍然是

4、Ferrers图象，这两个 Ferrers图象称为是一对共轭的Ferrers图象。,Ferrers图像证明正整数的无序分拆,整数n拆分成k个数的和的拆分数，和数n拆分成最大数为k的拆分数相等。因整数n拆分成k个数的和的拆分可用一k行的图像表示。所得的Ferrers图像的共轭图像最上面一行有k个格子。,Fibonacci数列,F0=0，F1=1，Fn=F(n-1)+F(n-2)（n=2，nN*）,Catalan数列,h(n)= h(0)*h(n-1)+h(1)*h(n-2) + . + h(n-1)h(0) (n=2) h(n)=h(n-1)*(4*n-2)/(n+1); h(n)=C(2n,n

5、)/(n+1) 入栈出栈序列,第一类Stirling数,第一类Stirling数是有正负的，其绝对值是包含n个元素的集合分作k个环排列的方法数目。 S(n,0) = 0, S(1,1) = 1. S(n+1,k) = S(n,k-1) + nS(n,k),第二类Stirling数,第二类Stirling数是把包含n个元素的集合划分为正好k个非空子集的方法的数目。 S(n,k)=0; (nk|k=0) S(n,n) = S(n,1) = 1, S(n,k) = S(n-1,k-1) + kS(n-1,k),母函数,对于任意数列a0,a1,a2.an 即用如下方法与一个函数联系起来： G(x) =

6、 a0 + a1x + a2x*2 + a3x3 +.+ anxn 则称G(x)是数列的生成函数(generating function) x+x2+x3+=1/(1-x),母函数求fibonacci数列的通项公式,g(x)=x+x2+2x3+3x4+5x5+8x6+13x7+. x*g(x)=x2+x3+2x4+3x5+5x6+8x7+. g(x)+x*g(x)=x+2x2+3x3+5x4+8x5+. g(x)+x*g(x)=g(x)/x-1 g(x)=x/(1-x-x2),幂级数展开的唯一性,鸽巢原理,（狄利克雷）抽屉原理 若有n个笼子和n+1只鸽子，所有的鸽子都被关在鸽笼里，那么至少有一

7、个笼子有至少2只鸽子。 Ramsey定理 在一个K6的完全图内，每边涂上红或蓝色，必然有一个红色的三角形或蓝色的三角形。,容斥原理,ZOJ 2836 Number Puzzle,题目大意：求m以下，能被集合A中任意元素整除的自然数有多少个？ 数据范围：n=|A|=10, m=2*109,Sample Input 3 22 3 7 3 62 3 7,Sample Output 1 4,容斥原理,sum=n; dfs(n,-1,0); void dfs(int n, int num, int pos) sum += n /num; for ( i = pos;i k;i + ) dfs(n , -

8、num*ai , i+1); ,群,群：给定一个集合G=a,b,c,和集合G上的二元运算，并满足: (a) 封闭性：a,bG, cG, ab=c。 (b) 结合律：a,b,cG, (ab)c=a(bc)。 (c) 单位元：eG, aG, ae=ea=a。 (d) 逆元：aG, bG, ab=ba=e，记b=a-1。 则称集合G在运算之下是一个群，简称G是群。一般ab简写为ab。,置换,置换：n个元素1,2,n之间的一个置换 表示1被1到n中的某个数a1取代，2被1到n中的某个数a2取代，直到n被1到n中的某个数an取代，且a1,a2,an互不相同。,置换,转0 a1= 转90 a2= 转180

9、 a3= 转270 a4=,置换群,置换群：置换群的元素是置换，运算是置换的连接。例如： 可以验证置换群满足群的四个条件。 上页中置换群G=转0、转90、转180、转270,不动置换类,Zk (K不动置换类)：设G是1n的置换群。若K是1n中某个元素，G中使K保持不变的置换的全体，记以Zk，叫做G中使K保持不动的置换类，简称K不动置换类。,对于方案1，四个置换都使方案1保持不变，所以Z1=a1, a2, a3, a4；对于方案3，只有置换a1使其不变，所以Z3=a1；对于方案11，置换a1和a3使方案其保持不变，所以Z11=a1, a3。,等价类,Ek(等价类)：设G是1n的置换群。若K是1n

10、中某个元素，K在G作用下的轨迹，记作Ek。即K在G的作用下所能变化成的所有元素的集合。,方案1在四个置换作用下都是方案1，所以E1=1；方案3，在a1下是3，在a2下变成6，在a3下变成5，在a4下变成4，所以E3=3,4,5,6；方案11，在a1、a3下是11，在a2、a4下变成12，所以E11=11,12。,Burnside引理,这里的L就是我们要求的互异的组合状态的个数。 D(aj) 表示在置换aj下不变的元素的个数,循环,称为n阶循环。每个置换都可以写若干互不相交的循环的乘积，两个循环(a1a2an)和(b1b2bn)互不相交是指aibj, i,j=1,2,n。例如： 这样的表示是唯一的。置换的循环节数是上述表示中循环的个数。例如(13)(25)(4)的循环节数为3。,Po