国家集训队2008论文集pálya计数法的应用

第1页，共14页Pólya计数法的应用南京外国语学校陈瑜希目录Pólya计数法的应用.................................................................................................................1目录...........................................................................................................................................1摘要...........................................................................................................................................2关键字.......................................................................................................................................2问题的提出...............................................................................................................................2[例一]He'sCirclesSGU294.........................................................................................2预备知识...................................................................................................................................3Burnside引理...........................................................................................................................4Pólya计数法............................................................................................................................6应用...........................................................................................................................................8[例二]CubesUVA10601.................................................................................................8[例三]TransportationisfunSPOJ419SPOJ422...................................................9[例四]IsomorphismSGU282........................................................................................11总结.........................................................................................................................................13参考文献.................................................................................................................................14第2页，共14页摘要在信息学竞赛中，我们会遇到许许多多的计数问题，很多问题看似困难，但熟练掌握Pólya计数法后，可以轻松解决。本文从一道信息学竞赛中出现的例题谈起，首先介绍了发现这题用普通计数法解决所遇到的困难，然后介绍了群、置换、置换群的基本概念、性质，并在此基础上引入Burnside定理，最后得出Pólya计数法，并给出证明。最后通过几道例题说明了Pólya计数法在信息学竞赛中的应用，并进行总结。关键字Burnside定理Pólya计数法问题的提出[例一]He'sCirclesSGU294有一个长度为N的环，上面写着’X’和’E’，问本质不同的环有多少种。(N不超过200000)。[分析]这个问题由于是一个环，许多未经过旋转时不同的方案，经过旋转之后就成了相同的方案，如果单纯的利用乘法原理来计算，无法排除这些相同的方案。如果想要用枚举法来做，需要枚举所有方案。枚举量不会低于本质不同的环的个数。事实证明，本质不同的环的个数是2n级别的。对于N=200000的数据规模，答案会有6万多位，显然枚举是行不通的。组合数学中，有一种计数法，可以很好的解决这类问题。第3页，共14页预备知识下面，我们介绍一种重要的计数工具——Pólya计数法。为了理解Pólya计数法，我们首先来看一下它所需要用到的概念。群给定一个集合G={a,b,c,…}和集合G上的二元运算，并满足:(a)封闭性：a,bG,cG,a*b=c。(b)结合律：a,b,cG,(a*b)*c=a*(b*c)。(c)单位元：eG,aG,a*e=e*a=a。(d)逆元：aG,bG,a*b=b*a=e，记b=a-1。则称集合G在运算*之下是一个群，简称G是群。一般a*b简写为ab。置换n个元素1,2,…,n之间的一个置换naaan2121表示1被1到n中的某个数a1取代，2被1到n中的某个数a2取代，直到n被1到n中的某个数an取代，且a1,a2,…,an互不相同。置换群置换群的元素是置换，运算是置换的连接。例如：1342432113424213421343211234432142134321可以验证置换群满足群的四个条件。例1中置换群G={转0格、转1格、转2格、转3格……转(n-1)格}nn212113221n24321n35421n……第4页，共14页2121nnnnBurnside引理介绍下面我们介绍Pólya计数法所要用到的一个引理——Burnside定理。用D(aj)表示在置换aj下不变的元素的个数。L表示本质不同的方案数。在例一中，对于N=4的情况。一共有4个置换：43214321143243212143432132144321所有方案在置换a1下都不变，D(a1)=16XXXX和EEEE在置换a2下不变，D(a2)=2XXXX和EEEE以及XEXE与EXEX在置换a3下不变，D(a3)=4XXXX和EEEE在置换a4下不变，D(a4)=2计算出6)24216(41L证明证明Burnside定理需要这样一个推论：设c为中的一种着色，那么与c等价的着色数等于G中的置换个数除以c的稳定核中的置换个数。定理1：对于每一种着色c，c的稳定核G(c)是一个置换群，而且对G中任意置换f与g,g*c=f*c当且仅当f-1g属于G(c)。证明：如果f和g都使c保持不变，则先f后g将使。保持不变，即(gf)(c)＝c。于是，在合成运算下，G(c)具有封闭性。显然，单位元使得所有着色不变。如果f使c不变，那么f-1也使c不变，于是G(c)具有对逆的封闭性。由于满足置换群定义的所有性质，所以，G(c)是一个置换群。sjjaDGL1)(||1第5页，共14页假设f*c=g*c则所以f-1g使c不变，因此，f-1。g属于G(c)，反之，假设f-1g属于G(c)，通过类似的计算可证得f*c=g*c作为定理1的一个推论，我们可以从已知的一种着色c出发，确定出在G的作用下不同的着色数。推论2：设c为中的一种着色，那么与c等价的着色数等于G中的置换个数除以c的稳定核中的置换个数，即证明：设f是G中的一个置换，根据定理1，满足g*c=f*c的置换g实际上就是中的那些置换。由消去律，则从fh=fh’得到h=h’。于是，集合中的置换个数等于G(c)中置换的个数。从而，对每个置换f，恰好存在|G(C)|个置换，这些置换作用在c上跟f有同样的效果。因为总共有|G|个置换，所以，与c等价的着色数等于有了这个推论，证明Burnside定理就是我们前面已多次用到的一些技巧的简单应用，即先采取两种不同的方式进行计数，然后使计数相等。究竟计什么数呢？我们要数使f保持c不变即f*c＝c的对偶(f,c)的个数。一种计数的方式是考察G中的每个f，并计算f保持着色不变的着色数，然后相加所有的量。因D(f)是通过f保持着色不变的着色集，所以用这种方式计数得到第6页，共14页另一种计数的方式是考察中的每个c，计算满足f*c=c的置换f的个数，然后相加所有的量。对每种着色，满足f*c＝c的所有f的集合就是我们所称的c的稳定核G(c)。因此，每个c对和的贡献是于是，用这种方式计数，得到但如果我们按等价类将着色归类，那么和式可以简化。在同一等价类中，两种着色对和贡献了同样的量，每个等价类的总贡献是|G|。由于等价类的个数就是不等价的着色数L，所以，等于L|G|解出L即得Pólya计数法介绍我们发现要计算D(aj)的值不是很容易，如果采用搜索的方法，总的时间规sjjaDGL1)(||1sjjaDGL1)(||1第7页，共14页模为O(nsp)。(n表示元素个数，s表示置换个数，p表示格子数，这里n的规模是很大的)下一步就是要找到一种简便的D(aj)的计算方法。先介绍一个循环的概念：循环：记称为n阶循环。每个置换都可以写若干互不相交的循环的乘积，两个循环(a1a2…an)和(b1b2…bn)互不相交是指aibj,i,j=1,2,…,n。例如：这样的表示是唯一的。置换的循环节数是上述表示中循环的个数。例如(13)(25)(4)的循环节数为3。设G是p个对象的一个置换群，用m种颜色涂染p个对象，则不同染色方案为：其中G={g1,…gs}c(gi)为置换gi的循环节数(i=1…s)在例一中，我们给N=4的环标号：1243构造置换群G'={g1,g2,g3,g4},｜G'｜＝4，令gi的循环节数为c(gi)(i=1,2,3,4)在G'的作用下，其中g1表示转0°,即g1=(1)(2)(3)(4)c(g1)=4g2表示转90°,即g2=(4321)c(g2)=1g3表示转180°,即g3=(13)(24)c(g3)=2g4表示转270°,即g4=(1234)c(g4)=12c(g1)=24=16=D(a1)2c(g2)=21=2=D(a2)2c(g3)=22=4=D(a3)2c(g4)=21=2=D(a4))mm(m||1)c(g)c(g)c(gs21