Burnside引理和Polya定理.ppt

* * 4.2 Burnside引理和Polya定理 预备知识 Burnside引理 Polya定理 母函数形式的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变到aj。 (1) 显然有 ； (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=2。 1 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 8 Sjk k aj 4 2 1 2 1 2 aj aj 1, k =k, 0, k ≠k. Sjk= 故由Burns