《信息竞赛中的组合数学》由会员分享，可在线阅读，更多相关《信息竞赛中的组合数学（35页珍藏版）》请在金锄头文库上搜索。
1、组合数学及其数学构造曹利国长沙市一中群群是集合G和其上的二元运算*, 并满足封闭性: 对于群里元素a, b, a*b也在G内)结合律: (a*b)*c = a*(b*c)单位元: 存在e, 对于每个元素a*e=e*a=a逆元: 对于每个元素a, 存在b使a*b=b*a=e, 记b=a-1一般简写a*b为ab置换用置换表示1被a1取代, 2被a2取代n被an取代. 其中a1, a2, an是1n的一个排列置换群置换群的元素是置换, 运算是置换的连接可以验证置换群满足群的四个条件循环n阶循环每个置换都可以写若干互不相交的循环的乘积， 例如表示是唯一的. 置换的循环节数是上述表示中循环的个数, 上例
2、的循环节数是3传球游戏n个人围成一圈, 每个人编号为1n. 有n个球, 编号也为1n. 一开始每人手里拿一个球基本操作为对传, 即a手里的球和b手里的球交换. 每个时间单位, 一个人可以不做任何动作, 或者与另外一人对传目标: 每个人拿到和自己编号相同的球问题1: 至少需要多少次对传?问题2: 至少需要多少时间?分析用置换表示初始状态每次对传相当于乘以一个对换置换可以唯一地表示成若干循环的乘积, 因此只考虑循环乘以对换(a, b)的结果a和b属于不同循环a个b属于同一个循环分析情况一: a和b属于不同循环因为循环的任何一个元素都可写成第一个,不妨设两个循环为(a, a1, a2, an)和(b
3、, b1, b2, , bm)结果为(b,b1,b2,bm,a,a1,a2,an)结论结论: 两个循环合并成一个两个循环合并成一个分析情况二: a和b属于同一个循环设为(a,a1,a2,ai,b,b1,b2,bm), 乘以(a,b)后变为(a,a1,a2,ai)(b,b1,b2,bm)可以这样理解: 乘以(a,b)是自身的逆操作结论结论: 一个循环拆为了两个一个循环拆为了两个分析问题1: 由于目标状态是(1)(2)(n), 所以需要不断的拆循环. 答案为n-c. 其中c为轮换个数问题2: 结论非常简单循环长度为1, 次数为0, 显然循环长度为2, 次数为1, 显然循环长度大于等于3的时候呢?分
4、析循环长度大于等于3, 次数为2. 对于循环(a1,a2,an), 只需要乘以(a2,an), 就变成了(a1,an)(a2,a3,an-1), 再乘以(a3,an-1), 就变成了(a2,an-1)(a3,a4,an-2)等等因此只需要乘以(a2,an)(a3,an-1)(a4,an-2)就可以得到(a1,an)(a2,an-1)(a3,an-2)再对换一次就可以了无聊的排序你弟弟有一项家庭作业需要你帮助完成。老师给了他一列数，需要他把这些数按升序排列。你可以每次交换两个数的位置，而一次交换的代价被定义成交换的两个数的和。写一个程序，用最小的交换代价和来帮助弟弟完成这项无聊的排序工作。分析从
5、初始状态变为目标状态可以看作完成一个置换. 把置换分解为s个不相交循环乘积各循环是独立的, 所以依次完成各个循环对于任意循环i, 设它的长度为ki, 容易证明至少需要交换ki-1次, 即每次让一个元素到达目标, 则前ki-1个元素到达目标后最后一个元素也到达目标分析显然每个元素至少参与一次交换. 既然交换次数一定, 应该让循环中的最小元素ti参加所有交换, 其他元素各只参加一次例如(8 2 7), 2占了7的位置, 则2和7交换; 2又占了8的位置, 则2和8交换花费为sumi+(ki-2)*ti,其中sumi为第i个循环所有数之和分析特殊情况: 先让ti和全局最小值m交换, 让m进入循环,
6、然后和所有元素交换一次后再和ti交换,花费为sumi+ti+(ki+1)m例如1,8,9,7,6,目标状态为1,6,7,8,9, 分解为(1)(8 6 9 7), 考虑第二个循环方案一: 花费为30 + (4-2)*6 = 42方案二: 花费为30 + 6 + (4+1)*1 = 41分析程序实现: 只需要记录每个循环节的长度ki和它的最小元素ti, 不需要模拟交换找循环最多访问每个元素一次, 时间复杂度是线性的同构计数一个竞赛图是这样的有向图任两个不同的点u、v之间有且只有一条边不存在自环用P表示对竞赛图顶点的一个置换。当任两个不同顶点u、v间直接相连的边的方向与顶点P(u)、P(v)间的一
7、样时，称该图在置换P下同构对给定的置换P，我们想知道对多少种竞赛图在置换P下同构同构计数例：有顶点1、2、3、4和置换P：P(1)=2，P(2)=4，P(3)=3，P(4)=1对于下图的四种竞赛图，在置换P下同构分析先把置换它分解成为循环, 首先证明长度为L的偶循环将导致无解对于点i1, 记P(ik)=ik+1, 假设i1和iL/2+1的边方向为i1-iL/2+1, 那么有i2-iL/2+2, i3-iL/2+3, , iL/2+1-i1, 和假设矛盾!假设确定其中k条独立边后其他边也会确定, 则答案为2k考虑两类边: 循环内边和循环间边. 分析循环内顶点的关系定了i1和ij之间的关系, ik
8、与i(k+j-2) mod n+1之间的关系也被确定下来了, 因此只需要确定i1和i2, i3, , i(L-1)/2+1这(L-1)/2对顶点的关系不同循环间顶点的关系设循环为(i1,i2,iL1)和(j1,j2,jL2), 通过类似分析得只需要确定gcd(L1, L2)对关系即可分析最后答案为2k1+k2其中k1=sum(L-1)/2, k2=sumgcd(L1, L2)可以用二分法加速求幂 Little rooks(SGU 222)中文大意：将k个车摆在n*n的棋盘上，使得任何两个车不能互相攻击（车可以横着或竖着走无限格，不能走斜线），求其放法总数。 算法描述 组合数学：排列与组合由于题
9、目里的棋子是“车”而不是“后”，所以一个棋子不会影响到与其不同行或与其不同列的棋子。结合n皇后问题的方案表示法，我们很容易想到排列组合。根据鸽巢原理n=k，先从简单的情况下手：n=k。此时的公式非常简单：P(n,k)。主要就是对于nk的情况时的处理。因为每一列最多只能放一颗棋子，所以我们首先把没有棋子的列去掉，再合并成一个n*k的棋盘，结合刚才的数据结构我们能很快知道在这个新棋盘上摆k个棋子还是P( n , k )种方案，再把去掉的(n-k+1)列插入摆棋子的k行中，插入方案总数易得为C( n , k )种。根据乘法原理，总方案数为C( n , k ) * P( n , k )种。这样一来程序
10、实现起来就方便多了。电子锁某机要部门安装了电子锁。M个工作人员每人发一张磁卡，卡上有开锁的密码特征。为了确保安全，规定至少要有N(=M)个人同时使用各自的磁卡才能将锁打开，并且任意N个人在一起都能将锁打开电子锁上至少要有多少种特征? 每个人的磁卡至少要有几个特征?彩票大街上到处在卖彩票，一元钱一张。购买撕开它上面的锡箔，你会看到一个漂亮的图案。图案有n种，如果你收集到所有n种彩票，就可以得大奖。请问，在平均情况下，需要买多少张彩票才能得到大奖呢？ 分析已经有k个图案, s=k/n, 拿到一个新的需要1次的概率: 1-s2次的概率: s*(1-s)t次的概率: st-1*(1-s)期望: 概率加
11、权和(1-s)*(1 + 2s + 3s2 + 4s3 + ) = (1-s)E而sE = s + 2s2 + 3s3 + = E-(1+s+s2+)移项得(1-s)E = 1+s+s2+=1/(1-s) = n/(n-k)分析总结已有0个图案: 拿1次就可以多搜集一个已有1个图案: 平均拿n/(n-1)次就可多搜集一个已有k个图案: 平均拿n/(n-k)次就可多搜集一个所以总次数为: n(1+1/2+1/3+1/n)着色问题对22的方阵用黑白两种颜色涂色，问能得到多少种不同的图像？经过顺时针旋转能吻合的两种方案算同一种方案原问题的置换给四个格子1，2，3，4着k=2种颜色用置换群定义定价类:
12、 置换一(转0度)： (1,2,3,4)置换二(转90度)：(2,3,4,1)置换三(转180度)：(3,4,1,2)置换四(转270度)：(4,1,2,3)G=转0度，转90度，转180度，转270度 Burnside引理对于一个置换f, 若方案s变换到自己, 称它为f的不动点. f的不动点数目记为C(f)Burnside引理: 等价类数目为C(f)的平均值考虑所有满足方案s是置换f的不动点的(s,f)对. 则数目= sumCf=sumZk假设有L个等价类, 由于处于同一个等价类的Zk相同, 因此sumZk中每个等价类可以合并在一起, 即sumEk*Zk, 其中每个等价类取一个k由基本定理,
13、 这个和为L*G. 因此L=sumCf/LBurnside引理计算举例置 换含 义该置换下不变的着色方案不动点数f1转01,2,3,4,5,6,7,8,9,10,11,12,13,14,15,1616f2转901,22f3转1801,2,11,124f4转2701,22故方案数为所有C(f)的平均数，即(16+2+4+2)/4=6，和枚举的结果一致 Plya定理Burnside定理需要计算每个置换f的不动点数目C(f)方案一: 对有所有着色方案, 检查它是否为f的不动点. 缺点: 着色方案非常多!方案二: 把f分解成循环的乘积. 不动点必然满足每个循环内的颜色相同. 如果有m(f)个循环, 则有km(f)个不动点方案二称为Polya定理Plya定理计算举例置 换含 义循环分解式M( f )（f的循环节）f1转0(1)(2)(3)(4)4f2转90(1234)1f3转180(13)(24)2f4转270(1432)1不同方案数为(24+21+22+21)/4=6 一般情况n*n的格子, 涂m种颜色分n为奇数和偶数两种情况讨论
