大学课件-Pólya原理及其应用-

由天下分享时间：2025/1/12 21:08:17 加入收藏我要投稿点赞

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之间的一个置换???1?a12?n??表示1被1到n?a2?an?中的某个数a1取代，2被1到n中的某个数a2取代，直到n被1到n中的某个数an取代，且a1,a2,…,an互不相同。本例中有4个置换：

?12345678910111213141516? 转0? a1=??12345678910111213141516??

?? 转90? a2=???12345678910111213141516?? ??12634510789121116131415??12345678910111213141516?转180? a3=??12563491078111215161314??

??转270? a4=???12345678910111213141516?? ??12456389107121114151613?置换群：置换群的元素是置换，运算是置换的连接。例如：

?1234??1234??1234??3124??1234???3124????4321?????3124????2431?????2431?? ??????????可以验证置换群满足群的四个条件。

本题中置换群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\\元素j aI a1 a2 a3 a4 │Zj│ 1 S1,1 S2,1 S3,1 S4,1 2 S1,2 S2,2 S3,2 S4,2 …… 16 D(ai) D(a1) D(a2) D(a3) D(a4) S1,16 …… S2,16 …… S3,16 …… S4,16 …… │Z1│ │Z2│ …… │Z16│ ??Z???D(a) jjj?1j?1164其中

?0当ai?Zj,即j在ai的变化下变动了Sij???1当ai?Zj,即j在ai的变化下没有变 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│。所以

nLL??Z???D(a)jij?1i?1ns?|Zk?1k|???|Zk|??|Ei|?|Zi|?L?|G|i?1k?Eii?1这里的L就是我们要求的互异的组合状态的个数。于是我们得出：

1n1sL?|Zk|?D(aj)??|G|k?1|G|j?1利用这个式子我们可以得到本题的解 L=(16+2+4+2)/4=6 与前面枚举得到的结果相吻合。这个式子叫做Burnside引理。

但是，我们发现要计算D(aj)的值不是很容易，如果采用搜索的方法，总的时间规模为O(n?s?p)。(n表示元素个数，s表示置换个数，p表示格子数，这里n的规模是很大的) 下一步就是要找到一种简便的D(aj)的计算方法。先介绍一个循环的概念：循环：记

?a1(a1a2?an)???a?2a2a3??an?1anan??a1??

称为n阶循环。每个置换都可以写若干互不相交的循环的乘积，两个循环(a1a2…an)和(b1b2…bn)互不相交是指ai?bj, i,j=1,2,…,n。例如：

?1??3?2531445???(13)(25)(4)?2?