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的格式可以表示为：k阶循环出现ck次用 来表示Sn中有相同格式的置换的全体构成一个共轭类置换p的循环格式 显然满足：定理：Sn中属于 共轭类的元素个数 为：证明：属于 共轭类的置换为： 中的点刚好是1到n的全排列但是有重复： (1) 由于(a1a2…ak)=(a2a3…aka1)=…=(aka1…ak-1)都 表示相同的k阶循环，重复了k次ck个k阶循环重 复了 次 (2) 由互不相交的ck个k阶循环乘积的可交换性引 起的，ck个k阶循环重复了ck!次因此属于共轭类的不同的置换的个数为：例如S4中(2)2共轭类中置换的个数为：它们是(12)(34)，(13)(24)，(14)(23)。
1)1(3)1共轭类中置换的个数为：它们是(123)，(132)，(124)，(142)，(134)，(143) ，(234)，(243)b) k不动置换类设G是[1,n]上的一个置换群，k∈[1,n]，G中使k保 持不变的置换全体，称为k不动置换类，记为Zk定理：置换群G的k不动置换类zk是G的一个子群 证明：(1) 封闭性： (3) 单位元：G中的单位元显然属于Zk；(2) 结合律显然；(4) 逆元：因此Zk是G的一个子群c) 等价类 考虑G= {(1)(2)(3)(4), (12), (34), (12)(34)} 在G的作用下，12能互相变换，但不能变到34； 同样的34能互相变换，但不能变到12 因此12属于同一类，34属于同一类 注意到k和l属于同一个等价类，或者说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不动置换类。
则有|Ek||Zk|=|G|, k=1,2,…n 证明：假设|Ek|=l，并不妨设Ek={a1=k, …,al}记ZkPj ={PPj | P∈Zk}，则PPj把k变到aj，这表明集合 ZkPj (j=1,2,…,l)互不相交考虑它们在同一个等价类，故存在置换Pj把k变到aj1) 显然有 ； (2) 对任意p∈G，它必把k变到某个aj，因此pPj-1把k 变到k，这说明pPj-1∈Zk，即p=PPj∈ZkPj因此有故2. Burnside引理定理(Burnside引理)：设G={a1,a2,…,ag}是[1,n]上的 置换群 把每个置换都写成不相交的循环的乘积则不同的等价类的个数L为：c1(ak)是在置换ak的作用下不动点的个数 [1,n]在G的作用下被分成一些等价类先用一个例子验证一下Burnside引理 对于置换群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=21 2 3 4 c1(aj) (1)(2)(3)(4) 1 1 1 1 4 (1) (12)(3)(4) 0 0 1 1 2 (1) (2) (1)(2)(34) 1 1 0 0 2 (1) (2) (12)(34) 0 0 0 0 0 (2)|Zk| → 2 2 2 2 8Sjk k aj 42 12 12ajaj1, k =k, 0, k ≠k.Sjk=故由Burnside引理可知：L=(4+2+2+0)/4=2。
以下表分析：其中：一般的，定义ajaj1, k =k, 0, k ≠k.Sjk=Sjk k aj1 2 … n c1(aj)a1 S11 S12 … S1n c1(a1)a2 S21 S22 … S2n c1(a2)… … … …ag Sg1 Sg2 … Sgn c1(ag)|Zk| |Z1| |Z2| … |Zn| ∑|Zk|= ∑c1(aj).gj=1nk=1 因此有设G把[1,n]分成的L个不同的等价类为F1,…,FL，即若i，j同属于一个等价类，则Ei=Ej，故|Ei|=|Ej|这表明，若i属于某一个等价类Fk，则Ei=Fk这样又由于|Ei||Zi|=|Ej||Zj|=|G|，可得|Zi|=|Zj|因此有：这样就证明了Burnside引理例1 4个相同格子，用白蓝两种颜色着色，有多少 种不同的方案？经过旋转后相同的方案算同一种1. 不动：a1=(1)(2)…(16)；1 2 3 4 5 6 7 89 10 11 12 13 14 15 162. 逆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引理要首先列出所有nm种可能的染色 方案，然后找出在每个置换下保持不变的方案数2) 颜色的数量m； (3) 置换群显然当m或n很大的时候，这个方法会非常繁琐我们希望找到其它的方法来计算c1(ak)从分析前例开始： a1=(1)(2)…(16)；1 2 11 12 a2=(1)(2)(3456)(78910)(1112)(13141516)；a4=(1)(2)(35)(46)(79)(810)(11)(12)(1315)(1416)；a3=(1)(2)(6543)(10987)(1112)(16151413)；对于a2和a3，在它们的作用下保持不变的图像是1和2 ，其共同点就是4个格子染同一种颜色(白或蓝)b a c d而在a4的作用下保持不变的图像是1,2,11,12，其共同 点是对角格子颜色相同(白白、蓝蓝、白蓝、蓝白)注意到a2,a3,a4分别表示逆时针转90,270,180度 如果这些旋转是直接作用在棋盘上，对应的置 换为a2’=(abcd)，a3’=(dcba)，a4’=(ac)(bd) 。
这表明：在置换ai的作用下保持不变的那些图像， 是在置换ai’中同一个循环节内的格子染相同的颜色 所得到的图像这样如果我们用c(ai’)表示置换ai’的循环节数，则有其中2代表白蓝两种颜色一般的如果有n个对象，m种颜色，共有mn种图像 对于某个转动群，设它作用在这些图像上所对应的 置换群为G={a1,…,ag}，直接作用在染色对象上的置 换群为G’={a1’,…,ag’}，则有这样Burnside引理就变成了如下的Polya定理：定理(Polya定理)：设G’是n个对象的一个置换群 用m种颜色去对这n个对象进行染色，则不同的方案 数为(在置换群G’的作用下变成相同的方案算是同一 种方案)：其中G’={a1’,…,ag’}，c(ai’)表示置换ai’的循环节数例2 等边三角形的三个顶点用红绿蓝三种颜色来着 色，有多少种不同的方案？保持不变的变换群包括：(1) 沿中心旋转0，120，240度；(2) 沿三条中线的翻转因此由Polya定理可知不同的方案数为：12 3例3 对正四面体的四个顶点用四种不同的颜色来着 色，有多少种不同的方案？使正四面体重合的运动群包括：因此由Polya定理可知不同的方案数为：12 34(1) 保持不变； (2) 沿过顶点和对面中心点的直 线旋转120，240度； (3) 沿过对边中点的直线旋转180度。
即例4 对正六面体的六个面用红蓝两种颜色来着色， 有多少种不同的方案？ 使正六面体的六个面保持不变的运动群包括： (1) 不变置换： (1)(2)(3)(4)(5)(6)； (2) 沿对面中心轴转动90，270度：(3) 沿对面中心轴转动180度：(1)(2345)(6)， (1)(5432)(6) (同类共6个)；(1)(24)(35)(6) (同类共3个)； (4) 沿对边中点轴转动180度：(16)(25)(43) (同类共6个)； (5) 沿对角线轴转动120，240度：(346)(152)，(643)(251) (同类共8个) 故例5 对正六面体的八个顶点用两种颜色着色，有多 少种不同的方案？ 使正六面体的八个顶点保持不变的运动群包括： (1) 不变置换： (1)(2)(3)(4)(5)(6)(7)(8)； (2) 沿对面中心轴转动90，270度：(3) 沿对面中心轴转动180度：(1234)(5678)， (4321)(8765) (同类共6个)；(13)(24)(57)(68) (同类共3个)； (4) 沿对边中点轴转动180度：(17)(26)(35)(48) (同类共6个)； (5) 沿对角线轴转动120，240度：(2)(136)(8)(475), (2)(631)(8)(574) (同类共8个)。
故例6 骰子的6个面分别有1,…,6点，有多少种不同的 方案？利用前题结论，用m种颜色染色不同的方案数为：即：L1=1, L2=10, L3=57, L4=240, L5=800, L6=2226设刚好用m种颜色的方案数为Nm，则：这相当于是对正六面体的六个面用六种颜色染色， 要求每种颜色刚好出现一次其中N1=L1=1由L1=1, L2=10, L3=57, L4=240, L5=800, L6=2226有实际上利用Burnside引理更方便首先考虑有多少种不同的图像 问题相当于对正六面体的六个面用六种颜色进行染 色，而且要求每种颜色刚好出现一次，因此不同的 图像有 6!=720但是保持正六面体重合的24种旋转置换中，只有不 动置换能保持图像不变，对于其它的置换，都没有 图像能保持不变因此由Burnside引理可知不同的方案数为：720/24=30例7 用3个红珠子，2个蓝珠子镶在正五边形的五个 顶点上，有多少种。