资源描述：
《Chap4-2Burnside引理、Polya定理.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、4.4Burnside引理S3={(1)(2)(3),(23),(13),(12),(123),(132)}.A3={(1)(2)(3),(123),(132)}.S4={(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),(123),(124),(132),(134),(142),(143),(234),(243),(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23)}.A4={(1)(2)(3)(4),(123),(124
2、),(132),(134),(142),(143),(234),(243),(12)(34),(13)(24),(14)(23)}.(1)共轭类先观察S3,A3,S4,A4,以增加感性认识。一般可把Sn中任意一个置换p分解成若干互不相交的循环乘积：4.4Burnside引理C1C2CnSn中p的循环格式(1)(2)…(n),满足Sn中有相同格式的置换全体构成一个共轭类。4.4Burnside引理4.4Burnside引理4.4Burnside引理4.4Burnside引理4.4Burnside引理设G是[1,n]上的一个置换群.G≤Sn.k∈
3、[1,n],G中使k保持不变的置换全体,称为k不动置换类,记做Zk.(2)k不动置换类定理置换群G的k不动置换类Zk是G的一个子群.P1P2P1P2封闭性：k→k→k,kk.结合性：自然。有单位元：G的单位元属于Zk.∴Zk≤G.G={(1)(2)(3)(4),(12),(34),(12)(34)}.在G作用下，1变2，3变4，但1不变到3。故12属于一类，34属于另一类。4.4Burnside引理(3)等价类先看一个例子由此可见，可以通过G将[1，n]的元素进行分类4.4Burnside引理k在G作用下的“轨迹”形成一个封闭的类。对于k,l
4、，若存在G中的一个置换把k变成l，则称它们属于同一个等价类。因此1到n的正整数可以按照群G的置换分成若干个等价类。数k所属的等价类记为Ek。4.4Burnside引理定理设G是[1,n]上的一个置换群，Ek是[1,n]在G的作用下包含k的等价类，Zk是k不动置换类。则有
5、Ek
6、
7、Zk
8、=
9、G
10、,k=1,2,…n证明：假设
11、Ek
12、＝l,不妨设Ek＝{a1=k,…,al}，互不相等的正整数。由于它们在同一个等价类，故存在置换Pj把k变到aj。考虑ZkPj4.4Burnside引理4.4Burnside引理(4)Burnside引理例如，G={e,
13、(12),(34),(12)(34)}.c1(a1)=4,c1(a2)=2,c1(a3)=2,c1(a4)=0.l=[4+2+2+0]/4=2.以本例列表分析：1234c1(aj)(1)(2)(3)(4)11114(1)(12)(3)(4)00112(1)(2)(1)(2)(34)11002(1)(2)(12)(34)00000(2)
14、Zk
15、→22228Sjkkaj4212124.4Burnside引理ajaj1,k=k,0,k≠k.Sjk=Sjkkaj12…nc1(aj)a1S11S12…S1nc1(a1)a2S21S22…S2nc1(a2
16、)…………agSg1Sg2…Sgnc1(ag)
17、Zk
18、
19、Z1
20、
21、Z2
22、…
23、Zn
24、∑
25、Zk
26、=∑c1(aj).gj=1nk=14.4Burnside引理一般而言，与上表相仿，有如下表格，其中ajaj1,k=k,0,k≠k.Sjk=4.4Burnside引理若i,j同属一个等价类，则Ei=Ej,
27、Ei
28、=
29、Ej
30、因
31、Ei
32、
33、Zi
34、=
35、G
36、,故
37、Zi
38、=
39、Zj
40、.所以设在G作用下，[1,n]分成l个等价类。[1,n]=E1+E2+…+El.例一正方形分成4格，2着色，有多少种方案？图象：看上去不同的图形。方案：经过转动相同的图象算同一方案。图象数总
41、是大于方案数。123456789101112131415164.4Burnside引理不动：p1=(1)(2)…(16)逆时针转90º：p2=(1)(2)(3456)(78910)(1112)(13141516)顺时针转90º：p3=(1)(2)(6543)(10987)(1112)(16151413)转180º：p4=(1)(2)(35)(46)(79)(810)(11)(12)(1315)(1416)(16+2+2+4)/4=6(种方案)4.4Burnside引理4.5Pólya定理Ω设G是以Ω为目标集的置换群，是某一转动群R的表示。G是
42、以M为目标集的置换群，是同一转动群R的表示。设Ω=[1,n],M={S1,S2,…Sm}是m种颜色的集合，对Ω中的元素用M中的颜色着色，得到的图象ΩΩnnn集合用M
