资源描述：
《Burnside引理与Polya定理》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。
1、第4章Burnside引理与Polya定理2021/10/182问题：用黑、白两种颜色对2×2棋盘的格子着色，问有几种不同的着色方案？引论C1C2C3C4C5C6C7C8C9C10C11C12C13C14C15C162021/10/183(1)若正方形的位置固定，则有16种不同的着色方案;(2)若正方形可以转动，则有6种不同的着色方案。Polya定理是解决不等价的诸物的记数问题。引论2021/10/184定义给定一个集合G和G上的一个二元运算*,若下列四个条件成立:(1)对任,有;(2)对任,有;(3)存在,对任有;(4)对
2、任,存在,使得则称集合G在运算*下构成一个群.或称代数结构是一个群。群2021/10/185基本性质:定理4.1群的单位元是唯一的。定理4.2如果是一个群，则对任,有(a)a*b=a*cb=c(b)b*a=c*ab=c定理4.3群中每一个元素的逆元素是唯一的。定理4.4如果是一个群，那么对任,有群2021/10/186定义设是一个群,H是G的非空子集,并满足以下条件:(1)若,则;(2)若,则;(3),e是的单位元则称为的子群。群2021/10/187定理设是有限群,H是G的非空子集，若H关于*封闭，则是的子群。证设
3、H
4、=
5、n。,中必有两个相等.设为,则.若,则由知若,则由知这就证明了对,有,故所以是的子群。群2021/10/188定义集合S上的双射函数P称为S上的一个置换。当S为无限集时,S上的置换称为无限次的。当S为n个元素的有限集时,则S上的置换称为n次的。n次置换一般记为其中为的一个排列.置换群2021/10/189例若S={1,2,3},那么S上的所有置换为设为{1,2,…,n}上的置换的全体，显然有。对任,定义它们的乘积为：置换群2021/10/1810例定理关于置换乘积运算构成群,称为n次对称群.证(1)封闭性:若,则,因而置换群
6、2021/10/1811(2)结合性:故(3)单位元:置换群2021/10/1812置换群(4)逆元素:的子群称为置换群。2021/10/1813一个置换可以表示为若干循环之积。定理4.6任何一个置换都可以表示为若干循环之积.证,考虑其中是第一次出现重复的元素。置换群2021/10/1814置换群下面证明。若不然,则有,使得,即有,但,这与p是单射相矛盾。具体分解过程:从1开始,考虑得到一个包含1的循环,若包含了所有的元素,则停止;2021/10/1815置换群否则,令是不在上述循环中的最小元素,构造得到包含的循环。这样继续
7、下去,直到所有的元素取完为止。例2021/10/18161.共轭类设G是的子群,对任,若存在,使得,则称s与t是G共轭的.G共轭关系是一个等价关系:(1)自反性:,有;(2)对称性:;(3)传递性:若,则Burnside引理2021/10/1817设Sn中置换p分解如下互不相交的循环之积:其中.若k阶循环出现的次数为,则称置换p的型(格式)为显然有.Burnside引理2021/10/1818Burnside引理例的型为引理两个置换是关于共轭的当且仅当它们是同型的.在Sn中同型置换的全体,称为与该型相应的共轭类.2021/1
8、0/1819定理4.9Sn中属于共轭类的置换个数为例S4中22共轭类有个置换.S4中1221共轭类有个置换。Burnside引理2021/10/18202.k不动置换类设G是{1,2,…,n}上的置换群,令称为G之k不动置换类.例若G={e,(12),(34),(12)(34)},则有Z1={e,(34)},Z2={e,(34)}Z3={e,(12)},Z4={e,(12)}Burnside引理2021/10/1821定理4.10群G的k不动置换类Zk是G之一个子群.证显然,故Zk非空.又若,由知,故Zk是G之一个子群。Bu
9、rnside引理2021/10/18223.等价类设G是S={1,2,…n}上的置换群,在S上定义G等价关系:对任,若存在,使得,则称是G等价的.定理4.10G等价关系是S上的等价关系.证(1)自反性:对任,有;(2)对称性:若,则(3)传递性:若,,则Burnside引理2021/10/1823元素k所在的等价类记为Ek。例若G={e,(12),(34),(12)(34)},那么有E1=E2={1,2},E3=E4={3,4}Burnside引理2021/10/1824习题4.84.102021/10/1825k不动置换类
10、设G是{1,2,…,n}上的置换群,令称为G之k不动置换类.例若G={e,(12),(34),(12)(34)},则有Z1={e,(34)},Z2={e,(34)}Z3={e,(12)},Z4={e,(12)}Burnside引理2021/10/1826等价类设G是S={1,2,…n}上的
