📄 4_4.htm
字号:
<html><head><title>Untitled Document</title><meta http-equiv="Content-Type" content="text/html; charset=gb2312"><link rel="stylesheet" href="../style.css"></head><body bgcolor="#FFFFFF"><h1>4.4 Burnside引理</h1><h4>(1)共轭类</h4><p>先观察S<sub>3</sub>,A<sub>3</sub>,S<sub>4</sub>,A<sub>4</sub>,以增加感性认识。<br>S<sub>3</sub>={(1)(2)(3),(23),(13),(123)(132)}.<br>A<sub>3</sub>={(1)(2)(3),(123),(132)}.<br>S<sub>4</sub>={(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)}.<br>A<sub>4</sub>={(1)(2)(3)(4),(123),(124),(132),(134),(142), (143),(234),(243),(12)(34),(13)(24),(14)(23)}.</p><p>S<sub>n</sub>中P的循环格式(1)<sup>C1</sup>(2)<sup>C2</sup>…(n)<sup>Cn</sup>,<img width=73 height=45 src="./4_4/image002.gif" align="middle"><br>S<sub>n</sub>中有相同格式的置换全体构成一个共轭类。</p><p><b>[定理1]</b>S<sub>n</sub>中属(1)<sup>C1</sup>(2)<sup>C2</sup>…(n)<sup>Cn</sup>共轭类的元的个数为<img width=149 height=45 src="./4_4/image004.gif" align="middle"></p><p><b>[证]</b>(1)<sup>C1</sup>(2)<sup>C2</sup>…(n)<sup>Cn</sup><br>一个长度为k的循环有k种表示，C<sub>k</sub>个长度为k的循环有C<sub>k</sub>!k<sup>Ck</sup>种表示.1,2,…,n的全排列共有n!个，给定一个排列，装入格式得一置换，除以前面的重复度得<img width=149 height=45 src="./4_4/image004.gif" align="middle">个不同的置换.</p><p><b>[例1]</b>S<sub>4</sub>中(2)<sup>2</sup>共轭类有4!/(2!2<sup>2</sup>)=3<br>(1)<sup>1</sup>(3)<sup>1</sup>共轭类有4!/(C1!C3!1<sup>C1</sup>3<sup>C3</sup>)=8<br>(1)<sup>1</sup>(2)<sup>1</sup>共轭类有4!/(C1!C2!1<sup>C1</sup>2<sup>C2</sup>)=6</p><h4>(2)k不动置换类</h4><p>设G是[1,n]上的一个置换群。G≤S<sub>n</sub>. K∈[1,n]<br>G中使k保持不变的置换全体，称为k不动置换类，记做Z<sub>k</sub>.</p><p><b>[定理]</b>置换群G的k不动置换类Z<sub>k</sub>是G的一个子群。</p><p>封闭性：<img width=120 height=21 src="./4_4/image006.gif" align="middle">,<img width=75 height=21 src="./4_4/image008.gif" align="middle">.<br>结合性：自然。<br>有单位元：G的单位元属于Z<sub>k</sub>.<br>有逆元：P∈Z<sub>k</sub>,<img width=64 height=21 src="./4_4/image010.gif" align="middle">,则<img width=73 height=24 src="./4_4/image012.gif" align="middle">,P∈Z<sub>k</sub>.<br>∴Z<sub>k</sub>≤G.</p><h4>(3)等价类</h4><p>举一个例子。<br>G={(1)(2)(3)(4),(12),(3 4),(1 2)(3 4)}.在G下，1变2，3变4，但1不变3。Z<sub>1</sub>=Z<sub>2</sub>={e,(3 4)}, Z<sub>3</sub>=Z<sub>4</sub>={e,(1 2)}.<br>对于A<sub>4</sub>, Z<sub>1</sub>={e,(2 3 4),(2 4 3)},Z<sub>2</sub>={e,(1 3 4),(1 4 3)} Z<sub>3</sub>={e,(1 2 4),(1 4 2)},Z<sub>4</sub>={e,(1 2 3),(1 3 2)}<br>一般[1,n]上G将[1,n]分成若干等价类，满足等价类的3个条件.(a)自反性;(b)对称性;(c)传递性。<br><b>一个由G定义的关系k</b>：<br>若存在p∈G,使得k→j<sup>p</sup>则称kR<sub>j</sub>.显然kR<sub>k</sub>；kR<sub>j</sub>则jR<sub>k</sub>；kR<sub>j</sub>,jR<sub>l</sub>则kR<sub>l</sub>。R是[1,n]上的一个等价关系。将[1,n]划分成若干等价类。<br>含目标集元素k的在G作用下的等价类也称为含k的轨道。</p><p><b>[定理]</b>设G是[1,n]上的一个置换群，E<sub>k</sub>是[1,n]在G的作用下包含k的等价类，Z<sub>k</sub>是k不动置换类。有|E<sub>k</sub>||Z<sub>k</sub>|=|G|. </p><p><b>[证]</b>设|E<sub>k</sub>|=l,E<sub>k</sub>={a<sub>1 </sub>(=k),a<sub>2</sub>,…,a<sub>l</sub>}, k=<img width=73 height=25 src="./4_4/image014.gif" align="middle">,i=1,2,…,l.<br>P={p<sub>1</sub>,p<sub>2</sub>,…,p<sub>l</sub>}令G<sub>i</sub>=Z<sub>k</sub>P<sub>i</sub>,i=1,2,…,l.<br>G<sub>i</sub>包含于G(G关于Zk的陪集分解)i≠j,G<sub>i</sub>∩G<sub>j</sub>=Φ. G<sub>1</sub>+G<sub>2</sub>+…+G<sub>l</sub>包含于G.<br>另一方面，任意P∈G. <img width=131 height=29 src="./4_4/image016.gif" align="middle">PP<sub>j</sub><sup>-1</sup>∈Z<sub>k</sub>, P∈Z<sub>k</sub>,P<sub>j</sub>=G<sub>j</sub>.<br>∴G包含于G<sub>1</sub>+…+G<sub>l</sub>.从而，G=G<sub>1</sub>+G<sub>2</sub>+…+G<sub>l</sub>.<br>|G|=|G<sub>1</sub>|+|G<sub>2</sub>|+…+|G<sub>l</sub>|=|Z<sub>k</sub>|·l= |Z<sub>k</sub>|·|E<sub>k</sub>|</p><h4>(4)Burnside引理</h4><p>设G={a<sub>1</sub>,a<sub>2</sub>,…a<sub>g</sub>}是目标集[1,n]上的置换群。每个置换都写成不相交循环的乘积。G将[1,n]换分成l个等价类。c1ak是在置换ak的作用下不动点的个数，也就是长度为1的循环的个数。<p><p><b>[Burnside引理]</b>l=[c<sub>1</sub>(a<sub>1</sub>)+c<sub>2</sub>(a<sub>2</sub>)+…+c<sub>g</sub>(a<sub>g</sub>)]/|G|</p><p>例如，G={e,(1 2),(3 4),(1 2)(3 4)}. c<sub>1</sub>(a<sub>1</sub>)=4,c<sub>1</sub>(a<sub>2</sub>)=2,c<sub>1</sub>(a<sub>3</sub>)=2,c<sub>1</sub>(a<sub>4</sub>)=0.<br>l=[4+2+2+0]/4=2.以本例列表分析：<br><table border=1><tr><td><img width=100 height=61 src="./4_4/pic002.gif" align="middle"></td><td>1 2 3 4</td><td>c<sub>1</sub>(a<sub>j</sub>)</td><td> </td></tr><tr align=center><td>(1)(2)(3)(4)<br>(1 2)(3)(4)<br>(1)(2)(3 4)<br>(1 2)(3 4)</td><td>1 1 1 1<br>0 0 1 1<br>1 1 0 0<br>0 0 0 0</td><td>4<br>2<br>2<br>0</td><td>(1)<sup>4</sup><br>(1)<sup>2</sup>(2)<sup>1</sup><br>(1)<sup>2</sup>(2)<sup>1</sup><br>(2)<sup>2</sup></td></tr><tr align=center><td>|Z<sub>k</sub>|→</td><td>2 2 2 2</td><td>8</td><td> </td></tr></table><img width=108 height=56 src="./4_4/image018.gif" align="middle"><br>对第j行求和得c1(aj),对第k列求和得|Zk| 表中元素的总和<img width=209 height=48 src="./4_4/image020.gif" align="middle">.</p><p>一般而言，与上表相仿，有下表，<table border=1><tr align=center><td><img width=100 height=61 src="./4_4/pic002.gif" align="middle"></td><td> 1 2 ... 4 </td><td>c<sub>1</sub>(a<sub>j</sub>)</td></tr><tr align=center><td>a<sub>1</sub><br>a<sub>2</sub><br>...<br>a<sub>g</sub></td><td>S<sub>11</sub> S<sub>12</sub> ... S<sub>1n</sub><br>S<sub>21</sub> S<sub>22</sub> ... S<sub>2n</sub><br>... ... ... ...<br>S<sub>g1</sub> S<sub>g2</sub> ... S<sub>gn</sub></td><td>c<sub>1</sub>(a<sub>1</sub>)<br>c<sub>1</sub>(a<sub>2</sub>)<br>...<br>c<sub>1</sub>(a<sub>g</sub>)</td></tr><tr align=center><td>|Z<sub>k</sub>|</td><td>|Z<sub>1</sub>||Z<sub>2</sub>|...|Z<sub>n</sub>|</td><td><img width=209 height=48 src="./4_4/image020.gif" align="middle"></td></tr></table>其中<img width=108 height=56 src="./4_4/image018.gif" align="middle"><br>∵<img width=101 height=45 src="./4_4/image022.gif" align="middle">,<img width=81 height=48 src="./4_4/image024.gif" align="middle">,设在G作用下，[1,n]分成l个等价类。[1,n]=E<sub>1</sub>+E<sub>2</sub>+…+E<sub>l</sub>.<br>若j,i同属一个等价类，则E<sub>i</sub>=E<sub>j</sub>,|E<sub>i</sub>|=|E<sub>j</sub>|因|E<sub>i</sub>||Z<sub>i</sub>|=|G|,故|Z<sub>i</sub>|=|Z<sub>j</sub>|.<br><img width=104 height=41 src="./4_4/image026.gif" align="middle"><br><img width=289 height=51 src="./4_4/image028.gif" align="middle"><br><img width=185 height=49 src="./4_4/image030.gif" align="middle"><br></p><p><b>[例2]</b>一正方形分成4格，2着色，有多少种方案？图象：看上去不同的图形。方案：经过转动相同的图象算同一方案。图象数总是大于方案数。</p><p><img width=339 height=97 src="./4_4/pic001.gif" align="middle"></p><p> 不动 ：p<sub>1</sub>=(1)(2)…(16)<br>逆时针转90<sup>。</sup>：p<sub>2</sub>=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16)<br>顺时针转90<sup>。</sup>：p<sub>3</sub>=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)<br> 转180<sup>。</sup>：p<sub>4</sub>=(1)(2)(3 5)(4 6)(7 9)(8 10)(11 12)(13 15)(14 16)<br>(16+2+2+4)/4=6(种方案)</p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -