资源描述：
《国家集训队2008论文集 pálya计数法应用》由会员上传分享，免费在线阅读，更多相关内容在学术论文-天天文库。
1、Pólya计数法的应用南京外国语学校陈瑜希目录Pólya计数法的应用1目录1摘要2关键字2问题的提出2[例一]He'sCirclesSGU2942预备知识3Burnside引理4Pólya计数法6应用9[例二]CubesUVA106019[例三]TransportationisfunSPOJ419SPOJ42210[例四]IsomorphismSGU28211总结14参考文献14第14页，共14页摘要在信息学竞赛中，我们会遇到许许多多的计数问题，很多问题看似困难，但熟练掌握Pólya计数法后，可以轻松解决。本文从一道
2、信息学竞赛中出现的例题谈起，首先介绍了发现这题用普通计数法解决所遇到的困难，然后介绍了群、置换、置换群的基本概念、性质，并在此基础上引入Burnside定理，最后得出Pólya计数法，并给出证明。最后通过几道例题说明了Pólya计数法在信息学竞赛中的应用，并进行总结。关键字Burnside定理Pólya计数法问题的提出[例一]He'sCirclesSGU294有一个长度为N的环，上面写着’X’和’E’，问本质不同的环有多少种。(N不超过200000)。[分析]这个问题由于是一个环，许多未经过旋转时不同的方案，经过旋转
3、之后就成了相同的方案，如果单纯的利用乘法原理来计算，无法排除这些相同的方案。如果想要用枚举法来做，需要枚举所有方案。枚举量不会低于本质不同的环的个数。事实证明，本质不同的环的个数是2n级别的。对于N=200000的数据规模，答案会有6万多位，显然枚举是行不通的。组合数学中，有一种计数法，可以很好的解决这类问题。第14页，共14页预备知识下面，我们介绍一种重要的计数工具——Pólya计数法。为了理解Pólya计数法，我们首先来看一下它所需要用到的概念。群给定一个集合G={a,b,c,…}和集合G上的二元运算，并满足:(
4、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之间的一个置换表示1被1到n中的某个数a1取代，2被1到n中的某个数a2取代，直到n被1到n中的某个数an取代，且a1,a2,…,an互不相同。置换群置换群的元素是置换，运算是置换的连接。例如：可以
5、验证置换群满足群的四个条件。例1中置换群G={转0格、转1格、转2格、转3格……转(n-1)格}……第14页，共14页Burnside引理介绍下面我们介绍Pólya计数法所要用到的一个引理——Burnside定理。用D(aj)表示在置换aj下不变的元素的个数。L表示本质不同的方案数。在例一中，对于N=4的情况。一共有4个置换：所有方案在置换a1下都不变，D(a1)=16XXXX和EEEE在置换a2下不变，D(a2)=2XXXX和EEEE以及XEXE与EXEX在置换a3下不变，D(a3)=4XXXX和EEEE在置换a4
6、下不变，D(a4)=2计算出证明证明Burnside定理需要这样一个推论：设c为中的一种着色，那么与c等价的着色数等于G中的置换个数除以c的稳定核中的置换个数。定理1：对于每一种着色c，c的稳定核G(c)是一个置换群，而且对G中任意置换f与g,g*c=f*c当且仅当f-1g属于G(c)。证明：如果f和g都使c保持不变，则先f后g将使。保持不变，即(gf)(c)＝c。于是，在合成运算下，G(c)具有封闭性。显然，单位元使得所有着色不变。如果f使c不变，那么f-1也使c不变，于是G(c)具有对逆的封闭性。由于满足置换群定
7、义的所有性质，所以，G(c)是一个置换群。第14页，共14页假设f*c=g*c则所以f-1g使c不变，因此，f-1。g属于G(c)，反之，假设f-1g属于G(c)，通过类似的计算可证得f*c=g*c作为定理1的一个推论，我们可以从已知的一种着色c出发，确定出在G的作用下不同的着色数。推论2：设c为中的一种着色，那么与c等价的着色数等于G中的置换个数除以c的稳定核中的置换个数，即证明：设f是G中的一个置换，根据定理1，满足g*c=f*c的置换g实际上就是中的那些置换。由消去律，则从fh=fh’得到h=h’。于是，集合中
8、的置换个数等于G(c)中置换的个数。从而，对每个置换f，恰好存在
9、G(C)
10、个置换，这些置换作用在c上跟f有同样的效果。因为总共有
11、G
12、个置换，所以，与c等价的着色数等于有了这个推论，证明Burnside定理就是我们前面已多次用到的一些技巧的简单应用，即先采取两种不同的方式进行计数，然后使计数相等。究竟计什么数呢？我们要数使f保持c不变即f*c
