符文杰-《Pólya原理及其应用》

Pólya原理及其应用华东师大二附中符文杰Pólya原理是组合数学中，用来计算全部互异的组合状态的个数的一个十分高效、简便的工具。下面，我就向大家介绍一下什么是Pólya原理以及它的应用。请先看下面这道例题：【例题1】对2*2的方阵用黑白两种颜色涂色，问能得到多少种不同的图像？经过旋转使之吻合的两种方案，算是同一种方案。【问题分析】由于该问题规模很小，我们可以先把所有的涂色方案列举出来。一个2*2的方阵的旋转方法一共有4种：旋转0度、旋转90度、旋转180度和旋转270度。(注：本文中默认旋转即为顺时针旋转)我们经过尝试，发现其中互异的一共只有6种：C3、C4、C5、C6是可以通过旋转相互变化而得，算作同一种；C7、C8、C9、C10是同一种；C11、C12是同一种；C13、C14、C15、C16也是同一种；C1和C2是各自独立的两种。于是，我们得到了下列6种不同的方案。但是，一旦这个问题由2*2的方阵变成20*20甚至200*200的方阵，我们就不能再一一枚举了，利用Pólya原理成了一个很好的解题方法。在接触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互不相同。本例中有4个置换：转0a1=1615141312111098765432116151413121110987654321转90a2=1514131611129871054362116151413121110987654321转180a3=1413161512118710943652116151413121110987654321转270a4=1316151411127109836542116151413121110987654321置换群：置换群的元素是置换，运算是置换的连接。例如：1342432113424213421343211234432142134321可以验证置换群满足群的四个条件。本题中置换群G={转0、转90、转180、转270}我们再看一个公式：│Ek│·│Zk│=│G│k=1…n该公式的一个很重要的研究对象是群的元素个数，有很大的用处。Zk(K不动置换类)：设G是1…n的置换群。若K是1…n中某个元素，G中使K保持不变的置换的全体，记以Zk，叫做G中使K保持不动的置换类，简称K不动置换类。如本例中：G是涂色方案1~16的置换群。对于方案1，四个置换都使方案1保持不变，所以Z1={a1,a2,a3,a4}；对于方案3，只有置换a1使其不变，所以Z3={a1}；对于方案11，置换a1和a3使方案其保持不变，所以Z11={a1,a3}。Ek(等价类)：设G是1…n的置换群。若K是1…n中某个元素，K在G作用下的轨迹，记作Ek。即K在G的作用下所能变化成的所有元素的集合。如本例中：方案1在四个置换作用下都是方案1，所以E1={1}；方案3，在a1下是3，在a2下变成6，在a3下变成5，在a4下变成4，所以E3={3,4,5,6}；方案11，在a1、a3下是11，在a2、a4下变成12，所以E11={11,12}。本例中的数据，也完全符合这个定理。如本例中：│E1│·│Z1│=14=4=│G││E3│·│Z3│=41=4=│G││E11│·│Z11│=22=4=│G│限于篇幅，这里就不对这个定理进行证明。接着就来研究每个元素在各个置换下不变的次数的总和。见下表：置换\Sij\元素jaI12……16D(ai)a1a2a3a4S1,1S2,1S3,1S4,1S1,2S2,2S3,2S4,2……………………S1,16S2,16S3,16S4,16D(a1)D(a2)D(a3)D(a4)│Zj││Z1││Z2│……│Z16│其中D(aj)表示在置换aj下不变的元素的个数如本题中：涂色方案1在a1下没变动，S1,1=1；方案3在a3变动了，S3,3=0；在置换a1的变化下16种方案都没变动，D(a1)=16；在置换a2下只有1、2这两种方案没变动，D(a2)=2。一般情况下，我们也可以得出这样的结论：我们对左式进行研究。不妨设N={1，……，n}中共有L个等价类，N=E1+E2+……+EL，则当j和k属于同一等价类时，有│Zj│=│Zk│。所以这里的L就是我们要求的互异的组合状态的个数。于是我们得出：利用这个式子我们可以得到本题的解L=(16+2+4+2)/4=6与前面枚举得到的结果相吻合。这个式子叫做Burnside引理。41161j)(ZjjjaD的变化下没有变在即当的变化下变动了在即当ijiijiijajZaajZaS,1,0|||||||||Z|111kGLZEZLiiiLiEkknkisiinjaD11j)(ZsjjnkkaDGZGL11)(||1||||1但是，我们发现要计算D(aj)的值不是很容易，如果采用搜索的方法，总的时间规模为O(nsp)。(n表示元素个数，s表示置换个数，p表示格子数，这里n的规模是很大的)下一步就是要找到一种简便的D(aj)的计算方法。先介绍一个循环的概念：循环：记13212121)(aaaaaaaaaaannnn称为n阶循环。每个置换都可以写若干互不相交的循环的乘积，两个循环(a1a2…an)和(b1b2…bn)互不相交是指aibj,i,j=1,2,…,n。例如：)4)(25)(13(2415354321这样的表示是唯一的。置换的循环节数是上述表示中循环的个数。例如(13)(25)(4)的循环节数为3。有了这些基础，就可以做进一步的研究，我们换一个角度来考虑这个问题。我们给2*2方阵的每个方块标号，如下图：2134构造置换群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)=1我们可以发现，gi的同一个循环节中的对象涂以相同的颜色所得的图像数mc(gi)正好对应Ｇ中置换ai作用下不变的图象数，即2c(g1)=24=16=D(a1)2c(g2)=21=2=D(a2)2c(g3)=22=4=D(a3)2c(g4)=21=2=D(a4)由此我们得出一个结论：设G是p个对象的一个置换群，用m种颜色涂染p个对象，则不同染色方案为：其中G={g1,…gs}c(gi)为置换gi的循环节数(i=1…s)这就是所谓的Pólya定理。我们发现利用Pólya定理的时间复杂度为O(sp)(这里s表示置换个数，p表示格子数)，与前面得到的Burnside引理相比之下，又有了很大的改进，其优越性就十分明显了。Pólya定理充分挖掘了研究对象的内在联系，总结了规律，省去了许多不必要的盲目搜索，把解决这类问题的时间规模降到了一个非常低的水平。现在我们把问题改为：nn的方阵，每个小格可涂m种颜色，求在旋转操作下本质不同的解的总数。【问题分析】先看一个很容易想到的搜索的方法。(见附录)这样搜索的效率是极低的，它还有很大的改进的余地。前面，我们采用的方法是先搜后判，这样的盲目性极高。我们需要边搜边判，避免过多的不必要的枚举，我们更希望把判断条件完全融入到搜索的边界中去，消灭无效的枚举。这个美好的希望是可以实现的。我们可以在方阵中分出互不重叠的长为[(n+1)/2]，宽为[n/2]的四个矩阵。当n为偶数时，恰好分完；当n为奇数时，剩下中心的一个格子，它在所有的旋转下都不动，所以它涂任何颜色都对其它格子没有影响。令m种颜色为0~m-1，我们把矩阵中的每格的颜色所代表的数字顺次(左上角从左到右，从上到下；右上角从上到下，从右到)mm(m||1)c(g)c(g)c(gs21GL左；……)排成m进制数，然后就可以表示为一个十进制数，其取值范围为0~m[n2/4]-1。(因为[n/2]*[(n+1)/2]=[n2/4])这样，我们就把一个方阵简化为4个整数。我们只要找到每一个等价类中左上角的数最大的那个方案(如果左上角相同，就顺时针方向顺次比较)这样，在枚举的时候其它三个数一定不大于左上角的数，效率应该是最高的。进一步考虑，当左上角数为i时,(0iR-1)令R=m[n2/4]可分为下列的4类：其它三个整数均小于i，共i3个。右上角为i，其它两个整数均小于i，共i2个。右上角、右下角为i，左下角不大于i，共i+1个。右下角为i，其它两个整数均小于i，且右上角的数不小于左下角的，共i(i+1)/2个。因此，当n为奇数时，还要乘一个m。由此我们就巧妙地得到了一个公式。但是，我们应该看到要想到这个公式需要很高的智能和付出不少的时间。另一方面，这种方法只能对这道题有用而不能广泛地应用于一类试题，具有很大的不定性因素。因此，如果能掌握一种适用面广的原理，就会对解这一类题有很大的帮助。下面我们就采用Pólya定理。我们可以分三步来解决这个问题。1．确定置换群)2(41)1(2123)12)(1(6123)1(41)23i23i()1)1(231)-(i23)1(()123i23(i))1(211ii(242211232310102323RRRRRRRRRRiiiiiiiLRiRiRiRi在这里很明显只有4个置换：转0、转90、转180、转270。所以，置换群G={转0、转90、转180、转270}。2．计算循环节个数首先，给每个格子顺次编号（1~n2），再开一个二维数组记录置换后的状态。最后通过搜索计算每个置换下的循环节个数，效率为一次方级。3．代入公式即利用Pólya定理得到最后结果。【程序题解】constmaxn=10;vara,b:array[1..maxn,1..maxn]ofinteger;{记录方阵的状态}i,j,m,n:integer;{m颜色数;n方阵大小}l,l1:longint;procedurexz;{将方阵旋转90}vari,j:integer;beginfori:=1tondoforj:=1tondoa[j,n+1-i]:=b[i,j];b:=aend;procedurexhj;{计算当前状态的循环节个数}vari,j,i1,j1,k,p:integer;begink:=0;{用来记录循环节个数，清零}fori:=1tondoforj:=1tondoifa[i,j]0then{搜索当前尚未访问过的格子}begininc(k);{循环节个数加1}i1:=(a[i,j]-1)divn;j1:=(a[i,j]-1)modn+1;{得到这个循环的下一个格子}a[i,j]:=0;{表示该格已访问}whilea[i1,j1]0dobegin)mm(m||1)c(g)c(g)c(gs21GLp:=a[i1,j1];{暂存当前格的信息}a[i1,j1]:=0;{置已访问