资源描述：
《经典黑书组合计数》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、2005年浙江省队培训 第2讲组合计数刘汝佳目录一、置换群二、组合数学基础三、生成函数四、等价类计数五、递推法一、置换群群群是集合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是1~n的一个排列置换群置换群的元素是置换,运算是置换的连接可以验证置换群满足群的四个条件定理设G是1…n的置换群,
2、K是1…n的某个元素G中使K保持不变的置换集合,记为Zk,称为K不动置换类K在G作用下的轨迹记为Ek,也就是通过置换G能变换到的元素集合定理:
3、Ek
4、*
5、Zk
6、=
7、G
8、(证明略)循环n阶循环每个置换都可以写若干互不相交的循环的乘积，例如表示是唯一的.置换的循环节数是上述表示中循环的个数,上例的循环节数是3传球游戏n个人围成一圈,每个人编号为1~n.有n个球,编号也为1~n.一开始每人手里拿一个球基本操作为对传,即a手里的球和b手里的球交换.每个时间单位,一个人可以不做任何动作,或者与另外一人对传目标:每个人拿到和自己编号相同的球问题1:至少需要多少次对传?
9、问题2:至少需要多少时间?分析用置换表示初始状态每次对传相当于乘以一个对换置换可以唯一地表示成若干循环的乘积,因此只考虑循环乘以对换(a,b)的结果a和b属于不同循环a个b属于同一个循环分析情况一:a和b属于不同循环因为循环的任何一个元素都可写成第一个,不妨设两个循环为(a,a1,a2,…an)和(b,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
10、,…,bm)可以这样理解:乘以(a,b)是自身的逆操作结论:一个循环拆为了两个分析问题1:由于目标状态是(1)(2)…(n),所以需要不断的拆循环.答案为n-c.其中c为轮换个数问题2:结论非常简单循环长度为1,次数为0,显然循环长度为2,次数为1,显然循环长度大于等于3的时候呢?分析循环长度大于等于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)(a
11、4,an-2)…就可以得到(a1,an)(a2,an-1)(a3,an-2)…再对换一次就可以了无聊的排序你弟弟有一项家庭作业需要你帮助完成。老师给了他一列数，需要他把这些数按升序排列。你可以每次交换两个数的位置，而一次交换的代价被定义成交换的两个数的和。写一个程序，用最小的交换代价和来帮助弟弟完成这项无聊的排序工作。分析从初始状态变为目标状态可以看作完成一个置换.把置换分解为s个不相交循环乘积各循环是独立的,所以依次完成各个循环对于任意循环i,设它的长度为ki,容易证明至少需要交换ki-1次,即每次让一个元素到达目标,则前ki-1个元素到达目标后最后一个
12、元素也到达目标分析显然每个元素至少参与一次交换.既然交换次数一定,应该让循环中的最小元素ti参加所有交换,其他元素各只参加一次例如(827),2占了7的位置,则2和7交换;2又占了8的位置,则2和8交换花费为sumi+(ki-2)*ti,其中sumi为第i个循环所有数之和分析特殊情况:先让ti和全局最小值m交换,让m进入循环,然后和所有元素交换一次后再和ti交换,花费为sumi+ti+(ki+1)m例如1,8,9,7,6,目标状态为1,6,7,8,9,分解为(1)(8697),考虑第二个循环方案一:花费为30+(4-2)*6=42方案二:花费为30+6+(
13、4+1)*1=41分析程序实现:只需要记录每个循环节的长度ki和它的最小元素ti,不需要模拟交换找循环最多访问每个元素一次,时间复杂度是线性的同构计数一个竞赛图是这样的有向图任两个不同的点u、v之间有且只有一条边不存在自环用P表示对竞赛图顶点的一个置换。当任两个不同顶点u、v间直接相连的边的方向与顶点P(u)、P(v)间的一样时，称该图在置换P下同构对给定的置换P，我们想知道对多少种竞赛图在置换P下同构同构计数例：有顶点1、2、3、4和置换P：P(1)=2，P(2)=4，P(3)=3，P(4)=1对于下图的四种竞赛图，在置换P下同构分析先把置换它分解成为循
14、环,首先证明长度为L的偶循环将导致无解对于点i1,记P(ik)=i
