Burnside引理和Polya定理

1、4.2 Burnside引理和引理和Polya定理定理1. 预备知识预备知识2. Burnside引理引理3. Polya定理定理4. 母函数形式的母函数形式的Polya定理定理1. 预备知识预备知识(a) 共轭类共轭类Sn中任意一个置换中任意一个置换p可分解成若干个互不相交的循可分解成若干个互不相交的循环的乘积：环的乘积：其中其中k1+k2+kt=n。设其中设其中k阶循环出现的次数为阶循环出现的次数为ck，k=1,2,n。这样置换这样置换p的格式可以表示为：的格式可以表示为：(.)(.).(.),tkkktpa aab bbh hh 12121212 k阶循环出现阶循环出现ck次用次用 来表

2、示。来表示。( )kck( ) ( ) .( ) .ncccn1212Sn中有相同格式的置换的全体构成一个中有相同格式的置换的全体构成一个共轭类共轭类。置换置换p的循环格式的循环格式 显然满足：显然满足：( ) ( ) .( )ncccn1212.nkkkcn 1定理定理：Sn中属于中属于 共轭类的元素个数共轭类的元素个数为：为：( ) ( ) .( )ncccn1212.!.!.ncccnnc ccn12121 2！证明：属于证明：属于 共轭类的置换为：共轭类的置换为： ( ) ( ) .( )ncccn1212( ).( )( ).( ).( .).( .)kkccc 1221 中的点刚好

3、是中的点刚好是1到到n的全排列。但是有重复：的全排列。但是有重复：.!.!.ncccnnc ccn12121 2！( ).( )( ).( ).( .).( .)kkccc 1221 (1) 由于由于(a1a2ak)=(a2a3aka1)=(aka1ak-1)都都表示相同的表示相同的k阶循环，重复了阶循环，重复了k次。次。ck个个k阶循环重阶循环重复了复了 次。次。kck(2) 由互不相交的由互不相交的ck个个k阶循环乘积的可交换性引阶循环乘积的可交换性引起的，起的，ck个个k阶循环重复了阶循环重复了ck!次。次。因此属于共轭类的不同的置换的个数为：因此属于共轭类的不同的置换的个数为：例如例如

4、S4中中(2)2共轭类中置换的个数为：共轭类中置换的个数为：,! 2432 2！它们是它们是(12)(34)，(13)(24)，(14)(23)。(1)1(3)1共轭类中置换的个数为：共轭类中置换的个数为：它们是它们是(123)，(132)，(124)，(142)，(134)，(143)，(234)，(243)。,! 1481 3！(b) k不动置换类不动置换类设设G是是1,n上的一个置换群，上的一个置换群，k1,n，G中使中使k保保持不变的置换全体，称为持不变的置换全体，称为k不动置换类不动置换类，记为，记为Zk。定理定理：置换群：置换群G的的k不动置换类不动置换类zk是是G的一个子群。的一

5、个子群。证明证明：(1) 封闭性：封闭性： (3) 单位元：单位元：G中的单位元显然属于中的单位元显然属于Zk；(2) 结合律显然；结合律显然；PPkkk 12P Pkk1 2(4) 逆元：逆元：Pkk Pkk 1因此因此Zk是是G的一个子群。的一个子群。(c) 等价类等价类考虑考虑G= (1)(2)(3)(4), (12), (34), (12)(34)。在在G的作用下，的作用下，12能互相变换，但不能变到能互相变换，但不能变到34；同样的同样的34能互相变换，但不能变到能互相变换，但不能变到12。因此因此12属于同一类，属于同一类，34属于同一类。属于同一类。 注意到注意到k和和l属于同一

6、个等价类，或者说属于同一个等价类，或者说Ek=El，当，当且仅当存在且仅当存在G的某个置换把的某个置换把k变到变到l。(群的封闭性群的封闭性)对于一般的置换群对于一般的置换群G，k在在G中置换的作用下的中置换的作用下的轨轨迹迹形成一个封闭的集合，称为形成一个封闭的集合，称为等价类等价类，记为，记为Ek。对于上例对于上例G= (1)(2)(3)(4), (12), (34), (12)(34)，显然有显然有E1=E2=1,2，E3=E4=3,4。定理定理：设设G是是1,n上的置换群，上的置换群，Ek是是1,n在在G的的作用下包含作用下包含k的等价类，的等价类，Zk是是k不动置换类。则有不动置换类

7、。则有 |Ek|Zk|=|G|, k=1,2,n。2. Burnside引理引理定理定理(Burnside引理引理)：设：设G=a1,a2,ag是是1,n上的上的置换群。置换群。把每个置换都写成不相交的循环的乘积。把每个置换都写成不相交的循环的乘积。则不同的等价类的个数则不同的等价类的个数L为：为：()().()|gLc ac ac aG111211c1(ak)是在置换是在置换ak的作用下不动点的个数。的作用下不动点的个数。1,n在在G的作用下被分成一些等价类。的作用下被分成一些等价类。()().() .gc ac ac ag111211先用一个例子验证一下先用一个例子验证一下Burnside

8、引理。引理。对于置换群对于置换群G=e，(12)，(34)，(12)(34)，又又c1(a1)=4，c1(a2)=2，c1(a3)=2，c1(a4)=0，我们知道我们知道E1=E2=1,2，E3=E4=3,4，即，即L=2。故由故由Burnside引理可知：引理可知：L=(4+2+2+0)/4=2。例例1 4个相同格子，用白蓝两种颜色着色，有多少个相同格子，用白蓝两种颜色着色，有多少种不同的方案？经过旋转后相同的方案算同一种。种不同的方案？经过旋转后相同的方案算同一种。1. 不动：不动：a1=(1)(2)(16)；1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 162.

9、 逆逆90度：度：a2=(1)(2)(3456)(78910)(1112)(13141516)；4. 180度：度： a4=(1)(2)(35)(46)(79)(810)(11)(12)(1315)(1416)；3. 顺顺90度：度：a3=(1)(2)(6543)(10987)(1112)(16151413)；因此不同的方案数为：因此不同的方案数为： (16+2+2+4)/4=6。3. Polya定理定理从上例中可以看出这类计数问题包含三个要素：从上例中可以看出这类计数问题包含三个要素：(1) 被染色物体被染色物体(如格子数如格子数n、形状等、形状等)；利用利用Burnside引理要首先列出所

10、有引理要首先列出所有nm种可能的染色种可能的染色方案，然后找出在每个置换下保持不变的方案数。方案，然后找出在每个置换下保持不变的方案数。(2) 颜色的数量颜色的数量m；(3) 置换群。置换群。显然当显然当m或或n很大的时候，这个方法会非常繁琐。很大的时候，这个方法会非常繁琐。()().()|gLc ac ac aG111211我们希望找到其它的方法来计算我们希望找到其它的方法来计算c1(ak)。从分析前例开始：从分析前例开始：a1=(1)(2)(16)；1 2 11 12a2=(1)(2)(3456)(78910)(1112)(13141516)；a4=(1)(2)(35)(46)(79)(8

11、10)(11)(12)(1315)(1416)；a3=(1)(2)(6543)(10987)(1112)(16151413)；对于对于a2和和a3，在它们的作用下保持不变的图像是，在它们的作用下保持不变的图像是1和和2，其共同点就是其共同点就是4个格子染同一种颜色个格子染同一种颜色(白或蓝白或蓝)。b ac d而在而在a4的作用下保持不变的图像是的作用下保持不变的图像是1,2,11,12，其共同，其共同点是对角格子颜色相同点是对角格子颜色相同(白白、蓝蓝、白蓝、蓝白白白、蓝蓝、白蓝、蓝白)。注意到注意到a2,a3,a4分别表示逆时针转分别表示逆时针转90,270,180度。度。如果这些旋转是直

12、接作用在棋盘上，对应的置如果这些旋转是直接作用在棋盘上，对应的置换为换为a2=(abcd)，a3=(dcba)，a4=(ac)(bd) 。这表明：这表明：在置换在置换ai的作用下保持不变的那些图像，的作用下保持不变的那些图像，是在置换是在置换ai中同一个循环节内的格子染相同的颜色中同一个循环节内的格子染相同的颜色所得到的图像所得到的图像。这样如果我们用这样如果我们用c(ai)表示置换表示置换ai的循环个数，则有的循环个数，则有其中其中2代表白蓝两种颜色。代表白蓝两种颜色。一般的如果有一般的如果有n个对象，个对象，m种颜色，共有种颜色，共有mn种图像。种图像。对于某个转动群，设它作用在这些图像上

13、所对应的对于某个转动群，设它作用在这些图像上所对应的置换群为置换群为G=a1,ag，直接作用在染色对象上的置，直接作用在染色对象上的置换群为换群为G=a1,ag，则有，则有ic aic a ()1()2,ic aic am ()1().这样这样Burnside引理引理就变成了如下的就变成了如下的Polya定理：定理：定理定理(Polya定理定理)：设：设G是是n个对象的一个置换群。个对象的一个置换群。用用m种颜色去对这种颜色去对这n个对象进行染色，则不同的方案个对象进行染色，则不同的方案数为数为(在置换群在置换群G的作用下变成相同的方案算是同一的作用下变成相同的方案算是同一种方案种方案)：()().()|gLc ac ac aG111211()()().|,gc ac ac aLmmmG121其中其中G=a1,ag，c(ai)表示置换表示置换ai的循环节数。的循环节数。例例2 等边三角形的三个顶点用红绿蓝三种颜色来着等边三角形的三个顶点用红绿蓝三种颜色来着