📄 4_5.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.5 Pólya定理</h1><p>设Ω=[1,n],M={S<sub>1</sub>,S<sub>2</sub>,…S<sub>m</sub>}是m种颜色的集合，对Ω中的元素用M中的颜色着色，得到的图象集合用M<sup>Ω</sup>表示，|M<sup>Ω</sup>|=m<sup>n</sup>,每个中的元素都有m种着色可能，n个元的着色有m<sup>n</sup>种可能。即共有m<sup>n</sup>个图象。<br>设<span class=overline>G</span>是以Ω为目标记得置换群，是某一转动群R的表示。G是以M<sup>Ω</sup>为目标记得置换群，是同一转动群R的表示。</p><p><span class=overline>G</span>≌R,G≌R，<span class=overline>G</span>≌G<br>一个着色图象在G的作用下变为另一个图象，则这两个图象属于同一方案。</p><p><b>[Pólya定理]</b>设<span class=overline>G</span>={<span class=overline>P</span><sub>1</sub>,<span class=overline>P</span><sub>2</sub>,…,<span class=overline>P</span><sub>g</sub>}是Ω上的一个置换群，C(<span class=overline>P</span><sub>k</sub>)是置换<span class=overline>P</span><sub>k</sub>的循环的个数，用M中的颜色对Ω中的元着色，着色方案数为l=<img width=200 height=49 src="./4_5/image002.gif" align="middle">.</p><p>f:Ω→M,G是作用在图象集合M<sup>Ω</sup>上的置换群。<br>对于<span class=overline>P</span>∈<span class=overline>G</span>,<span class=overline>P</span>=<img width=37 height=51 src="./4_5/image004.gif" align="middle">,k=1,2,…,n<br>T:<span class=overline>P</span>→P,P=<img width=40 height=53 src="./4_5/image006.gif" align="middle">,i=1,2,…,m<sup>n</sup><br>T:G→G <img width=92 height=33 src="./4_5/image008.gif" align="bottom">,i=1,2,…,m<sup>n</sup>, k=1,…,n.<br>P称为由<span class=overline>P</span>诱导出的M<sup>Ω</sup>上的置换。<br><span class=overline>G</span>={<span class=overline>P</span><sub>1</sub>,<span class=overline>P</span><sub>2</sub>,…,<span class=overline>P</span><sub>g</sub>},G={P<sub>1</sub>,P<sub>2</sub>,…,P<sub>g</sub>}<br>T是<span class=overline>G</span>到G的同构映射。<img width=95 height=27 src="./4_5/image010.gif" align="middle"></p><p>在P<sub>i</sub>作用下M<sup>Ω</sup>中的不动图象的个数<img width=95 height=27 src="./4_5/image010.gif" align="middle">，C(<span class=overline>P</span><sub>i</sub>)表示<span class=overline>P</span><sub>i</sub>的循环的个数，即同一循环中的元素都着同一种颜色的图象在P<sub>i</sub>的作用下保持不变。</p><p>对应于<span class=overline>P</span>∈<span class=overline>G</span>,有P∈G,P是M<sup>Ω</sup>(图象集)上的一个置换。现在要计算的也就是图象集在G作用下的等价类的个数。下面对前例进行分析，然后推导到一般。</p><p><span class=overline>P</span><sub>1</sub>=(1)(2)(3)(4),P<sub>1</sub>=(1)(2)…(16)<br><span class=overline>P</span><sub>2</sub>=(4 3 2 1), P<sub>2</sub>=(1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16)<br><span class=overline>P</span><sub>3</sub>=(1 2 3 4), P<sub>3</sub>=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)<br><span class=overline>P</span><sub>4</sub>=(1 3)(2 4), P<sub>4</sub>=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12)(13 15)(14 16)<br>C(<span class=overline>P</span><sub>1</sub>)=4,C<sub>1</sub>(P<sub>1</sub>)=16=2<sup>4</sup><br>C(<span class=overline>P</span><sub>2</sub>)=1,C<sub>1</sub>(P<sub>2</sub>)=2=2<sup>1</sup><br>C(<span class=overline>P</span><sub>3</sub>)=1,C<sub>1</sub>(P<sub>3</sub>)=2=2<sup>1</sup><br>C(<span class=overline>P</span><sub>4</sub>)=2,C<sub>1</sub>(P<sub>4</sub>)=4=2<sup>2</sup><br>求着色的方案数也即求图象的等价类个数。按Burside定理，求等价类的个数归结为每个置换下的不动点(不动图象)的个数。</p><p><b>[证]</b>对Ω的n个目标用m种颜色着色的图象集为M<sup>Ω</sup> |M<sup>|Ω|</sup>|=|M|<sup>Ω</sup>=m<sup>n</sup><br><span class=overline>G</span>的每一个元<span class=overline>P</span><sub>i</sub>是Ω上的一个置换，也对应了M<sup>Ω</sup>上的一个置换P<sub>i</sub>,这样<span class=overline>G</span>≌G,T:<span class=overline>P</span><sub>i</sub>←→P<sub>i</sub>在P<sub>i</sub>的作用下不动图象的个数C<sub>1</sub>(P<sub>i</sub>)等于<span class=overline>P</span><sub>i</sub>的同一循环中的目标都着相同色的选择的个数。即<img width=95 height=27 src="./4_5/image010.gif" align="middle">。因而在G的作用下，M<sup>Ω</sup>(图象)的等价类的个数。 <br>l=<img width=208 height=47 src="./4_5/image012.gif" align="middle">=<img width=200 height=49 src="./4_5/image002.gif" align="middle">. </p></body></html>⌨️ 快捷键说明
复制代码
Ctrl + C
搜索代码
Ctrl + F
全屏模式
F11
切换主题
Ctrl + Shift + D
显示快捷键
?
增大字号
Ctrl + =
减小字号
Ctrl + -