acm之组合数学

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

1、组合数学湖南师范大学罗迅排列集合中有n个元素，从该集合中有顺序的无重复取r个，称之为排列。P(n,r)=n!/(n-r)!有顺序的有重复nr有顺序无重复的环形排列P(n,r)/r组合n元素的集合，取出r个元素，不考虑秩序，称之为组合C(n,r)=n!/(n-r)!/r!也记作帕斯卡递推：C(n,r)=C(n-1,r-1)+C(n-1,r)题目列表POJ1496POJ1850hdu1465，错排问题，基本题容斥原理最简单的表述一般表述DeMorgan定理容斥原理容斥原理递归实现dfs(intidx,setS,intsym)ans+=nu

2、m(S)*sym;for(inti=idx;i

3、称出的质量有多少种？母函数普通型母函数一个6面骰子，连续掷10次，点数之和为30的概率是多少？母函数指数型母函数指数型母函数用来求多重集合的排列问题。给定集合S={n1a1,n2a2,…,nnan}，从中选取k个元素的排列数与x的k次方相关指数型母函数指数型母函数三个1，两个6,一个8，能够组成多少个四位数？母函数Note：答案不是x的4次方的系数！！！题目列表hdu1028，求整数拆分数，基本题hdu1085hdu1398，求整数拆分的变种hdu1521，指数型母函数，基本题hdu2079群群是带运算的集合，是一种代数结构给定一个集

4、合G，以及G上的一个二元运算如果运算满足封闭性结合性单位元存在逆元存在称G是一个群置换群置换是一个操作置换群就是有关置换的集合置换Note：置换是一种变换，跟数出现的顺序无关轮换称为一个轮换不是所有置换都是轮换但所有置换都可以分解为轮换的运算置换-轮换因为任意置换都可以划分为轮换，因此我们使用轮换来表示置换，比原始表达要方便Polya定理设D是一个有限集，包含p个对象G是D上的一个置换群R是一个有限权集，共有m个权问：用R给D赋权，共有多少种不同的方法gi是G中的第i个元素，也就是第i个置换c(g)是g分解出轮换的个数Polya定理示

5、例计算互异的组合状态计数问题Polya定理示例D是一个有限集，一共4个元素R是有限权集，一共2个权，也就是2种颜色G是D上的置换群，一共有4个置换a/b/c/d分别是4个置换的轮换的个数Polya定理示例旋转0°，置换为(1)(2)(3)(4)，轮换数量为4旋转90，置换为(1234)，轮换数量为1旋转180，置换为(13)(24)，轮换数量为2旋转270，置换为(1432)，轮换数量为1例2等边三角形的三个顶点用三种颜色染色，一共有多少种方案？D是有限集，一共3个元素R是权集，一共3个元素G是置换群，一共6个置换分别是(1)(2)(

6、3)、(123)、(132)、(1)(23)、(13)(2)、(12)(3)题目列表POJ1286POJ2409hdu1812，以上为最基本题POJ2154，略微优化Burnside引理设G是置换群，g是G中的一个置换，则G的等价类个数为e(g)表示g中不变元的个数Burnside引理示例此时n为16旋转0°，置换为单位元，不变元的个数为16旋转90，不变元的个数为2旋转180，不变元的个数为4旋转270，不变元的个数为2L=6Burnside与Polya置换群G是一样的置换的对象不一样Polya有限集D，含有p个元素权集R，含有m个

7、元素置换D，g的轮换数量由D决定用m与g的轮换数量计算BurnsideD与R共同构成RD置换RD，g的不变元个数由RD决定用不变元的数量进行计算