数学组合数学级学习教案.pptx

《数学组合数学级学习教案.pptx》由会员分享，可在线阅读，更多相关《数学组合数学级学习教案.pptx（61页珍藏版）》请在淘文阁 - 分享文档赚钱的网站上搜索。

1、数学数学(shxu)组合数学组合数学(shxu)级级第一页，共61页。7.1 群论基础群论基础(jch)7.1.1 7.1.1 群的定义群的定义 定义定义7.1.17.1.1代数系统（代数系统（GG，）若满足以下条件：）若满足以下条件：（1 1）结合律：对任意）结合律：对任意a a，b b，c Gc G，（a b)c=a(b c);a b)c=a(b c);（2 2）GG中有一个元素中有一个元素e e，适合对于，适合对于GG中任意元素中任意元素a a，都有，都有 ea=ae=a ea=ae=a （3 3）对于）对于GG中任意中任意a a，都可找到，都可找到GG中一个元素中一个元素a-1a-1，

2、满足，满足aa-1=a-1a=eaa-1=a-1a=e，则称（则称（GG，）为群。元素）为群。元素e e称为称为GG的单位元素，的单位元素，a-1a-1称为称为a a的逆元素。如果群的逆元素。如果群GG包含的元素个数有限，则包含的元素个数有限，则称称GG为有限群，否则称为有限群，否则称GG为无限为无限(wxin)(wxin)群。群。若只有（若只有（1 1）成立，称（）成立，称（GG，）为半群。）为半群。第1页/共61页第二页，共61页。例例例例7.1.1 7.1.1 设设设设Z Z为整数集，为整数集，为整数集，为整数集，+、是数的加法和乘法，则是数的加法和乘法，则是数的加法和乘法，则是数的加法

3、和乘法，则（1 1）（）（）（）（Z Z，+）是群，称为整数加法群。因为存在元素）是群，称为整数加法群。因为存在元素）是群，称为整数加法群。因为存在元素）是群，称为整数加法群。因为存在元素0 0，适合对于，适合对于，适合对于，适合对于Z Z中任意元素中任意元素中任意元素中任意元素a a，都有，都有，都有，都有0+a=a+0=a0+a=a+0=a，即，即，即，即0 0为单位元素；且对于为单位元素；且对于为单位元素；且对于为单位元素；且对于Z Z中任中任中任中任意意意意a a，都可找到，都可找到，都可找到，都可找到Z Z中一个元素中一个元素中一个元素中一个元素-a-a（a a的相反数），满足的相反

4、数），满足的相反数），满足的相反数），满足a+a+（-a-a）=（-a a）+a=0+a=0，即，即，即，即-a-a为为为为a a的逆元素。的逆元素。的逆元素。的逆元素。（2 2）（）（）（）（Z Z，）不是群。因为虽然）不是群。因为虽然）不是群。因为虽然）不是群。因为虽然(surn)(surn)存在单位元素存在单位元素存在单位元素存在单位元素e e，适合对，适合对，适合对，适合对于于于于Z Z中任意元素中任意元素中任意元素中任意元素a a，都有，都有，都有，都有1a=a1=a1a=a1=a，但除了，但除了，但除了，但除了1 1和和和和-1-1外，其它元素均外，其它元素均外，其它元素均外，其它

5、元素均无逆元素。无逆元素。无逆元素。无逆元素。第2页/共61页第三页，共61页。例例7.1.2 7.1.2 设设QQ为所有有理数组成的集合，为所有有理数组成的集合，R R为所为所有实数组成的集合，有实数组成的集合，C C为所有复数组成的集合；为所有复数组成的集合；Q*Q*为所有非零有理数组成的集合，为所有非零有理数组成的集合，R*R*为所有非为所有非零实数组成的集合，零实数组成的集合，C*C*为所有非零复数组成的集为所有非零复数组成的集合，合，+、是数的加法是数的加法(jif)(jif)和乘法，则和乘法，则 （QQ，+）、（）、（R R，+）、（）、（C C，+）都是群；）都是群；（QQ，）、

6、（）、（R R，）、（）、（C C，）都不是群，）都不是群，因为因为0 0无逆元素；无逆元素；（Q*Q*，）、（）、（R*R*，）、（）、（C*C*，）都是群。）都是群。第3页/共61页第四页，共61页。例例例例7.1.3 7.1.3 设设设设S S是一个非空集合，是一个非空集合，是一个非空集合，是一个非空集合，（S S）是是是是S S的幂的幂的幂的幂集，集，集，集，和和和和是是是是（S S）上的交运算和并运算，则）上的交运算和并运算，则）上的交运算和并运算，则）上的交运算和并运算，则 （1 1）（）（）（）（S S），），），），）不是群，虽然存在单位）不是群，虽然存在单位）不是群，虽然存在

7、单位）不是群，虽然存在单位(dnwi)(dnwi)元素元素元素元素S S，但不是任意元素都存在逆元素；，但不是任意元素都存在逆元素；，但不是任意元素都存在逆元素；，但不是任意元素都存在逆元素；（2 2）（）（）（）（S S），），），），）也不是群，虽然存在单位）也不是群，虽然存在单位）也不是群，虽然存在单位）也不是群，虽然存在单位(dnwi)(dnwi)元素：空集，但不是任意元素都存在逆元素：空集，但不是任意元素都存在逆元素：空集，但不是任意元素都存在逆元素：空集，但不是任意元素都存在逆元素。元素。元素。元素。例例例例7.1.4 7.1.4 设设设设A A是实数域上所有是实数域上所有是实数域

8、上所有是实数域上所有n n阶非奇异矩阵的集合，阶非奇异矩阵的集合，阶非奇异矩阵的集合，阶非奇异矩阵的集合，*为矩阵的乘法，不难验证（为矩阵的乘法，不难验证（为矩阵的乘法，不难验证（为矩阵的乘法，不难验证（A A，*）是群。是群。是群。是群。第4页/共61页第五页，共61页。定理定理定理定理7.1.1 7.1.1 群具有以下性质：群具有以下性质：群具有以下性质：群具有以下性质：单位元单位元单位元单位元e e唯一；唯一；唯一；唯一；逆元唯一；逆元唯一；逆元唯一；逆元唯一；满足消去律：即对满足消去律：即对满足消去律：即对满足消去律：即对a a，b b，c cGG，若，若，若，若ababacac，则，

9、则，则，则b bc c；若；若；若；若babacaca，则仍，则仍，则仍，则仍有有有有b bc c；a a，b bGG，则，则，则，则(ab)-1(ab)-1b-1a-1 b-1a-1，更一般有，更一般有，更一般有，更一般有(abc)-1(abc)-1c-1b-1a-1c-1b-1a-1；若若若若GG是有限是有限是有限是有限(yuxin)(yuxin)群，则对任意群，则对任意群，则对任意群，则对任意a aGG，必存在一个最小常数，必存在一个最小常数，必存在一个最小常数，必存在一个最小常数r r，使，使，使，使arare e，从而，从而，从而，从而a-1a-1ar-1ar-1。r r称为元素称为

10、元素称为元素称为元素a a的阶。的阶。的阶。的阶。7.1.2 群的性质群的性质(xngzh)第5页/共61页第六页，共61页。定理定理定理定理7.1.2 7.1.2 设设设设GG是一个群，在一个乘积是一个群，在一个乘积是一个群，在一个乘积是一个群，在一个乘积a1ana1an中可以任意中可以任意中可以任意中可以任意加括号而求其值。加括号而求其值。加括号而求其值。加括号而求其值。证明：证明：证明：证明：要证定理，只要证明任意加括号而得的积等于按要证定理，只要证明任意加括号而得的积等于按要证定理，只要证明任意加括号而得的积等于按要证定理，只要证明任意加括号而得的积等于按次序由左而右加括号所得的积次序

11、由左而右加括号所得的积次序由左而右加括号所得的积次序由左而右加括号所得的积 （a1a2a1a2）a3a3）an-1an-1）an an （7.1.17.1.1）（7.1.17.1.1）式对于）式对于）式对于）式对于(duy)n=1(duy)n=1，2 2不成问题；对于不成问题；对于不成问题；对于不成问题；对于(duy)n=3(duy)n=3，由结合律也不成问题。现在对，由结合律也不成问题。现在对，由结合律也不成问题。现在对，由结合律也不成问题。现在对n n用归纳法，用归纳法，用归纳法，用归纳法，假定对少于假定对少于假定对少于假定对少于n n个因子的乘积（个因子的乘积（个因子的乘积（个因子的乘积

12、（7.1.17.1.1）式成立，试证对）式成立，试证对）式成立，试证对）式成立，试证对n n个个个个因子的乘积（因子的乘积（因子的乘积（因子的乘积（7.1.17.1.1）式也成立。设有由）式也成立。设有由）式也成立。设有由）式也成立。设有由a1ana1an任意加括任意加括任意加括任意加括号而得到的乘积号而得到的乘积号而得到的乘积号而得到的乘积A A，求证，求证，求证，求证A A等于（等于（等于（等于（7.1.17.1.1）式。）式。）式。）式。设在设在设在设在A A中最后一次计算是前后两部分中最后一次计算是前后两部分中最后一次计算是前后两部分中最后一次计算是前后两部分B B与与与与C C相乘：

13、相乘：相乘：相乘：A=A=（B B）（C C）第6页/共61页第七页，共61页。今今C C的因子的因子(ynz)(ynz)个数小于个数小于n n，故由归纳假设，故由归纳假设，C C等于按次序自左而右加等于按次序自左而右加括号所得的乘积（括号所得的乘积（D D）anan。由结合律，。由结合律，A=A=（B B）（C C）=（B B）（D D）anan）=（B B）（D D）anan。但。但（B B）（D D）的因子）的因子(ynz)(ynz)个数小于个数小于n n，故由归纳假设，（，故由归纳假设，（B B）（D D）等于按次序由左而右加括号所得的乘积等于按次序由左而右加括号所得的乘积 （B B）

14、（D D）=（a1a2a1a2）a3a3）an-2an-2）an-1an-1 因而因而A=A=（B B）（D D）anan =（a1a2a1a2）a3a3）an-2an-2）an-1an-1）anan 即即A A等于（等于（7.1.17.1.1）式。）式。n n个个a a连乘所得的积称为连乘所得的积称为a a的的n n次方，记为次方，记为anan。我们规定我们规定a0=1a0=1，a-n=a-n=（anan）-1-1。aman=am+n aman=am+n，（，（amam）n=amnn=amn。第7页/共61页第八页，共61页。定义7.1.2设（G，）是一个(y)群，H是G的一个(y)子集，如

15、果按照G中的乘法运算，H仍是一个(y)群，则（H，）叫做（G，）的子群。如果G的一个(y)子群H不等于G，即HG，则（H，）叫做（G，）的真子群。第8页/共61页第九页，共61页。例例7.1.5 所有整数按照加法作所有整数按照加法作成一个群。对于任意整数成一个群。对于任意整数m，m的所有倍数的所有倍数(bish)在加法在加法下作成整数加法群的一个子群。下作成整数加法群的一个子群。例例7.1.6 任选群任选群G的一个元素的一个元素a，设，设a的阶为的阶为r，则，则Ha，a2，a r-1，are是是G的子的子群。这样的群群。这样的群H是由某个固定是由某个固定元素元素a的乘方组成的，成为循的乘方组成

16、的，成为循环群，或称环群，或称H是由元素是由元素a生成生成的群，的群，a叫做叫做H的生成元。的生成元。第9页/共61页第十页，共61页。定理定理定理定理7.1.2 7.1.2 有限群的阶数必能被其子群的阶数整有限群的阶数必能被其子群的阶数整有限群的阶数必能被其子群的阶数整有限群的阶数必能被其子群的阶数整除。除。除。除。定义定义定义定义7.1.3 7.1.3 若群（若群（若群（若群（GG，）的运算）的运算）的运算）的运算 适合交换律，适合交换律，适合交换律，适合交换律，则称（则称（则称（则称（GG，）为）为）为）为AbelAbel群或交换群群或交换群群或交换群群或交换群定理定理定理定理7.1.3

17、 7.1.3 在一个在一个在一个在一个AbelAbel群（群（群（群（GG，）中，一个乘）中，一个乘）中，一个乘）中，一个乘积积积积(chngj)(chngj)可以任意颠倒因子的次序而求真值。可以任意颠倒因子的次序而求真值。可以任意颠倒因子的次序而求真值。可以任意颠倒因子的次序而求真值。如果群如果群如果群如果群GG的运算不写作乘的运算不写作乘的运算不写作乘的运算不写作乘 而写作加而写作加而写作加而写作加+，则，则，则，则GG叫做一个加法群，我们一直假定一个加法群是叫做一个加法群，我们一直假定一个加法群是叫做一个加法群，我们一直假定一个加法群是叫做一个加法群，我们一直假定一个加法群是一个一个一个

18、一个AbelAbel群：群：群：群：a+b=b+a a+b=b+a 在乘法群中写做在乘法群中写做在乘法群中写做在乘法群中写做1 1的现在写做的现在写做的现在写做的现在写做0 0：a+0=a a+0=a第10页/共61页第十一页，共61页。在乘法群中写做a-1而称为(chn wi)a的逆的，现在写做-a而称为(chn wi)a的负：a+（-a）=0n为任意整数时，在乘法群中写作an而称为(chn wi)a的n次方的，现在写做na而称为(chn wi)a的n倍。三个指数律现在成为下面的形式：（m+n）a=ma+na，m（a+b）=ma+mb，m（na）=（mn）a。第11页/共61页第十二页，共6

19、1页。7.2置换群置换群 重要的一类群重要的一类群 一方面，任何有限群都可以用一方面，任何有限群都可以用它表示；它表示；另一方面，在伽罗瓦理论中它另一方面，在伽罗瓦理论中它起关键作用。起关键作用。它还在本章的它还在本章的Burnside引理及引理及Plya定理定理(dngl)中起着基本中起着基本作用。作用。第12页/共61页第十三页，共61页。定义定义定义定义7.2.1 7.2.1 设设设设MM是一个非空的有限是一个非空的有限是一个非空的有限是一个非空的有限(yuxin)(yuxin)集合，集合，集合，集合，MM的一个一对一变换称为一个置换。的一个一对一变换称为一个置换。的一个一对一变换称为一

20、个置换。的一个一对一变换称为一个置换。设设设设MM的元素为的元素为的元素为的元素为a1a1，a2a2，anan，则，则，则，则MM的置换的置换的置换的置换 可以可以可以可以简记为简记为简记为简记为 ，bi=bi=（aiai），），），），i=1i=1，22，n n的每个置换对应的每个置换对应的每个置换对应的每个置换对应a1a1，a2 a2，an an的一个排列，的一个排列，的一个排列，的一个排列，不同的置换对应不同的排列不同的置换对应不同的排列不同的置换对应不同的排列不同的置换对应不同的排列;此外，此外，此外，此外，a1a1，a2 a2，an an的任意排列也确定的任意排列也确定的任意排列也确

21、定的任意排列也确定MM的的的的一个置换一个置换一个置换一个置换.所以，所以，所以，所以，MM的置换共有的置换共有的置换共有的置换共有n n！个，其中！个，其中！个，其中！个，其中n n是是是是MM的元数，的元数，的元数，的元数，MM上的置换也称为上的置换也称为上的置换也称为上的置换也称为n n元置换。以下用元置换。以下用元置换。以下用元置换。以下用SnSn表示这表示这表示这表示这n n！个置换作成的集合。个置换作成的集合。个置换作成的集合。个置换作成的集合。第13页/共61页第十四页，共61页。例例例例7.2.1 7.2.1 设设设设M=1M=1，2 2，33，则有，则有，则有，则有3 3！=

22、6=6个个个个3 3元置换，元置换，元置换，元置换，11 为为为为3 3元恒等置换，元恒等置换，元恒等置换，元恒等置换，2=2=类似地可以类似地可以类似地可以类似地可以(ky)(ky)得到得到得到得到33，4 4，5 5，6 6。故，故，故，故，S3=1S3=1，22，33，44，55，66。对对对对MM中任意元素中任意元素中任意元素中任意元素a a及及及及MM的任意两个置换的任意两个置换的任意两个置换的任意两个置换，规定，规定，规定，规定（a a）=（a a）。）。）。）。例例例例7.2.2 7.2.2 设设设设 ，则则则则=。第14页/共61页第十五页，共61页。置换的乘法有下述一些性质置

23、换的乘法有下述一些性质(xngzh)(xngzh)：(1)(1)满足结合律：（满足结合律：（）=（），），(2)n (2)n元恒等置换是元恒等置换是SnSn中的单位元素中的单位元素e e，设，设为为00，有：，有：0=0 0=0。(3)(3)每个每个n n元置换在元置换在Sn Sn 中都有逆元素中都有逆元素 称为(chn wi)n元恒等置换。第15页/共61页第十六页，共61页。定理定理定理定理7.2.1 n7.2.1 n元置换的全体作成的集合元置换的全体作成的集合元置换的全体作成的集合元置换的全体作成的集合SnSn对置对置对置对置换的乘法作成一个群，称为换的乘法作成一个群，称为换的乘法作成一

24、个群，称为换的乘法作成一个群，称为n n 次对称群。次对称群。次对称群。次对称群。另外一方面，置换群的运算和理论也是对另外一方面，置换群的运算和理论也是对另外一方面，置换群的运算和理论也是对另外一方面，置换群的运算和理论也是对称图形运算和计数的基本工具。称图形运算和计数的基本工具。称图形运算和计数的基本工具。称图形运算和计数的基本工具。例例例例7.2.37.2.3将顶点分别为将顶点分别为将顶点分别为将顶点分别为1 1，2 2，3 3的正三角形（见的正三角形（见的正三角形（见的正三角形（见图图图图7.2.17.2.1）绕中心）绕中心）绕中心）绕中心OO沿逆时针方向分别旋转沿逆时针方向分别旋转沿逆

25、时针方向分别旋转沿逆时针方向分别旋转00、120120、240240，可看成，可看成，可看成，可看成(kn chn)(kn chn)顶点集顶点集顶点集顶点集11，2 2，33的置换，则有的置换，则有的置换，则有的置换，则有（1 1）旋转对称关系）旋转对称关系）旋转对称关系）旋转对称关系 e e，（转（转（转（转00）,（转（转（转（转120120）（转（转（转（转240240）第16页/共61页第十七页，共61页。21BCA3图图7.2.12逆时针旋转(xunzhun)第17页/共61页第十八页，共61页。（2 2）翻转）翻转(fn zhun)(fn zhun)对称关系，即将三角形对称关系，即

26、将三角形123123分别分别绕对称轴绕对称轴1A1A、2B2B、3C3C翻转翻转(fn zhun)180(fn zhun)180得顶点集得顶点集的另一类置换：的另一类置换：（绕（绕3C3C）（绕（绕2B2B）（绕（绕1A1A）因此，描述正三角形的全部对称关系，对应以上六种置换。连续两次对称映射对应两个置换的乘积，则置换集在置换乘法(chngf)下构成一个三次对称群S3。21BCA3图图7.2.1第18页/共61页第十九页，共61页。定义定义定义定义7.2.2 7.2.2 设设设设 是是是是MM的置换，若可取到的置换，若可取到的置换，若可取到的置换，若可取到MM的元素的元素的元素的元素a1a1，

27、arar使使使使（a1a1）a2a2，（a2a2）=a3=a3，（ar-1ar-1）=ar=ar，（arar）=a1=a1，而，而，而，而 不变不变不变不变MM的其余的其余的其余的其余的元素，则的元素，则的元素，则的元素，则 称为一个称为一个称为一个称为一个(y)(y)轮换，轮换，轮换，轮换，记为记为记为记为 （a1 a2 ar a1 a2 ar）当然可以把当然可以把当然可以把当然可以把a1a1，arar中的任意元素中的任意元素中的任意元素中的任意元素aiai排在头一排在头一排在头一排在头一位而改写成位而改写成位而改写成位而改写成 （ai ai+1 ar a1 ai-1ai ai+1 ar a

28、1 ai-1）例例例例7.2.4 =7.2.4 =（1 3 41 3 4）=（3 4 13 4 1）=（4 1 34 1 3）。）。）。）。定义定义定义定义7.2.3 M7.2.3 M的两个轮换的两个轮换的两个轮换的两个轮换=（a1ara1ar）和）和）和）和=（b1bsb1bs）说是不相杂或不相交，如果）说是不相杂或不相交，如果）说是不相杂或不相交，如果）说是不相杂或不相交，如果 a1 a1，ar ar和和和和b1b1，bsbs都不相同。都不相同。都不相同。都不相同。第19页/共61页第二十页，共61页。定理定理定理定理7.2.27.2.2若若若若 和和和和 是两个不相杂的轮换，则其乘法适合

29、交换律，是两个不相杂的轮换，则其乘法适合交换律，是两个不相杂的轮换，则其乘法适合交换律，是两个不相杂的轮换，则其乘法适合交换律，即即即即=定理定理定理定理7.2.37.2.3任意置换任意置换任意置换任意置换 恰有一法写成不相杂的轮换乘积。恰有一法写成不相杂的轮换乘积。恰有一法写成不相杂的轮换乘积。恰有一法写成不相杂的轮换乘积。证明：先证证明：先证证明：先证证明：先证 可以写成不相杂的轮换的乘积，取任意可以写成不相杂的轮换的乘积，取任意可以写成不相杂的轮换的乘积，取任意可以写成不相杂的轮换的乘积，取任意a1a1MM。（1 1）若）若）若）若（a1a1）=a1=a1，则，则，则，则a1a1自己就作

30、成一个轮换。自己就作成一个轮换。自己就作成一个轮换。自己就作成一个轮换。（2 2）设）设）设）设（a1a1）=a2=a2，（a2a2）=a3=a3，。这样下去，由于。这样下去，由于。这样下去，由于。这样下去，由于MM有限有限有限有限(yuxin)(yuxin)，故到某一个元素，故到某一个元素，故到某一个元素，故到某一个元素arar，其，其，其，其（arar）必然不能再是）必然不能再是）必然不能再是）必然不能再是新的元素，即这新的元素，即这新的元素，即这新的元素，即这（arar）必在）必在）必在）必在a1a1，arar之内。由于之内。由于之内。由于之内。由于 是一对是一对是一对是一对一的，我们已

31、有一的，我们已有一的，我们已有一的，我们已有（aiai）=ai+1=ai+1，i=1i=1，2 2，r-1r-1，所以，所以，所以，所以（arar）只能是）只能是）只能是）只能是a1a1。于是我们得到一个轮换（。于是我们得到一个轮换（。于是我们得到一个轮换（。于是我们得到一个轮换（a1ara1ar）。若）。若）。若）。若MM已经没有另外的元素，则已经没有另外的元素，则已经没有另外的元素，则已经没有另外的元素，则 就等于这个轮换，否则设就等于这个轮换，否则设就等于这个轮换，否则设就等于这个轮换，否则设b1b1不在不在不在不在a1a1，arar之内，则同样作法又可得到一个轮换（之内，则同样作法又可

32、得到一个轮换（之内，则同样作法又可得到一个轮换（之内，则同样作法又可得到一个轮换（b1bsb1bs）。因）。因）。因）。因为为为为a1a1，arar各自已有变到它的元素，所以各自已有变到它的元素，所以各自已有变到它的元素，所以各自已有变到它的元素，所以b1b1，bsbs中不会中不会中不会中不会有有有有a1a1，arar出现，即这两个轮换不相杂。若出现，即这两个轮换不相杂。若出现，即这两个轮换不相杂。若出现，即这两个轮换不相杂。若MM的元素已尽，的元素已尽，的元素已尽，的元素已尽，则则则则 就等于这两个轮换的乘积，否则如上又可得到一个轮换。就等于这两个轮换的乘积，否则如上又可得到一个轮换。就等于

33、这两个轮换的乘积，否则如上又可得到一个轮换。就等于这两个轮换的乘积，否则如上又可得到一个轮换。如此类推，由于如此类推，由于如此类推，由于如此类推，由于MM有限有限有限有限(yuxin)(yuxin)，最后必得，最后必得，最后必得，最后必得 第20页/共61页第二十一页，共61页。=（a1ar a1ar）（）（b1bsb1bs）（c1ctc1ct）（7.2.17.2.1）即即 表成了不相杂的轮换的乘积。表成了不相杂的轮换的乘积。今证表法唯一，设今证表法唯一，设 又可表为不相杂的轮换的乘积如下：又可表为不相杂的轮换的乘积如下：=（a1ar a1ar）（）（b1bsb1bs）（c1ctc1ct）（7

34、.2.27.2.2）看（看（7.2.17.2.1）式中的任意轮换，例如（）式中的任意轮换，例如（a1ara1ar）。）。a1 a1必出现在（必出现在（7.2.27.2.2）式）式中的某个轮换之内，例如（中的某个轮换之内，例如（a1ara1ar）。）。由于一个轮换中任意元素都可排在头一位，不妨假定由于一个轮换中任意元素都可排在头一位，不妨假定a1a1aa。于是，。于是，a2=a2=（a1a1）=（a1a1）=a2=a2，a3=a3=（a2a2）=（a2a2）=a3=a3，如此类，如此类推，可见（推，可见（a1ara1ar）必和（）必和（a1ara1ar）完全相同，这就是说，（）完全相同，这就是说

35、，（7.2.17.2.1）中的任意轮换必出现在（中的任意轮换必出现在（7.2.27.2.2）中，同样（）中，同样（7.2.27.2.2）中的任意轮换必出现）中的任意轮换必出现在（在（7.2.17.2.1）中，因之，（）中，因之，（7.2.17.2.1）和（）和（7.2.27.2.2）一样，最多排列在方法不同，）一样，最多排列在方法不同，但不相杂的轮换相乘适合交换律，所以但不相杂的轮换相乘适合交换律，所以(suy)(suy)排列的次序本来是可以任排列的次序本来是可以任意颠倒的。意颠倒的。第21页/共61页第二十二页，共61页。定义定义7.2.4 设（设（a1a2ar）为一）为一轮换轮换(lnhu

36、n)，我们称，我们称r为该轮为该轮换换(lnhun)的长度，一轮换的长度，一轮换(lnhun)的长度也就是其中所的长度也就是其中所含的元素个数。一般地，我们称含的元素个数。一般地，我们称长度为长度为r的轮换的轮换(lnhun)为为r阶阶轮换轮换(lnhun)。特别，长度为特别，长度为2的轮换的轮换(lnhun)称为对换。根据公式称为对换。根据公式7.2.3可知，可知，任意置换都可写成对换的乘积。任意置换都可写成对换的乘积。（a1a2ar）（a1a2）（）（a1 a3）（a1ar-1）（）（a1ar）（7.2.3）于是由定理于是由定理7.2.3即可推知下列即可推知下列推论。推论。第22页/共61

37、页第二十三页，共61页。推论推论7.2.3对任意置换，有一法（但未必只对任意置换，有一法（但未必只有一法）可将其写成一些对换的乘积。有一法）可将其写成一些对换的乘积。定义定义7.2.5 可以分解为奇数个对换之积的置可以分解为奇数个对换之积的置换称为奇置换，可以分解为偶数个对换之积换称为奇置换，可以分解为偶数个对换之积的置换称为偶置换。的置换称为偶置换。定理定理7.2.4 Sn中所有偶置换的构成中所有偶置换的构成(guchng)一个一个n！/2阶的子群阶的子群,称为交错称为交错群群,记为记为An。第23页/共61页第二十四页，共61页。7.3 7.3 BurnsideBurnside引理引理 7

38、.3.1 7.3.1 共轭类共轭类共轭类共轭类定义定义定义定义7.3.1 7.3.1 若若若若n n次置换可表示为互不交杂次置换可表示为互不交杂次置换可表示为互不交杂次置换可表示为互不交杂C1C1个个个个1 1轮换，轮换，轮换，轮换，C2C2个个个个2 2轮换，轮换，轮换，轮换，CnCn个个个个n n轮换的乘积，则此置换轮换的乘积，则此置换轮换的乘积，则此置换轮换的乘积，则此置换 称为称为称为称为(chn wi)(chn wi)（C1C1，C2C2，C nC n）类型，或）类型，或）类型，或）类型，或(1)(1)C1 (2)C2(n)Cn C1 (2)C2(n)Cn 类型。类型。类型。类型。显

39、然，显然，显然，显然，第24页/共61页第二十五页，共61页。例例7.3.1（1）（）（2 3 4）（）（5 6 7）属于）属于11203240506070类型，简写为（类型，简写为（1132）。）。例例7.3.2 3次对称群次对称群S3中所有置换中所有置换(zhhun)的类型是满足方程的类型是满足方程C11C22C333的所有非负整数解（见表的所有非负整数解（见表7.3.1）：）：（C1，C2，C3）属于）属于（3，0，0），（），（1，1，0），（），（0，0，1）第25页/共61页第二十六页，共61页。定义定义定义定义(dngy)7.3.2(dngy)7.3.2 置换群置换群置换群置换群

40、GG中属于同一类型中属于同一类型中属于同一类型中属于同一类型（C1,C2,CnC1,C2,Cn）的全体置换，叫做该类型相应的共）的全体置换，叫做该类型相应的共）的全体置换，叫做该类型相应的共）的全体置换，叫做该类型相应的共轭类，记为轭类，记为轭类，记为轭类，记为D D（C1,C2,CnC1,C2,Cn）。例例例例7.3.37.3.3将将将将S3S3按共轭类分成三类，见表按共轭类分成三类，见表按共轭类分成三类，见表按共轭类分成三类，见表7.3.17.3.1。类（C1,C2,Cn）类中置换类中元素数（3，0，0）（1）（2）（3）1（1，1，0）（1 2）（3），（1 3）（2），（1）（2 3）

41、3（0，0，1）（1 2 3），（1 3 2）2第26页/共61页第二十七页，共61页。定理定理(dngl)7.3.1 Sn中属中属(1)(2)(n)共轭类的个共轭类的个数为数为C1 C2 Cn n！C1!C2!Cn!1 2 n C1 C2 Cn第27页/共61页第二十八页，共61页。证(1)(2)(n)即 C1 C2 Cn()()()()()()_/1个 _/2个 _/n个_ _/C1个_ _/C2个_ _/Cn个 1）一个长度为k的循环有k种表示，2）Ck个长度为k的循环有Ck!种。因此Ck个k阶循环在排列时有Ck!kCk个表示。1,2,n的全排列共有n!个，给定一个排列，装入格式(g s

42、hi)得一置换。除以这些重复度得 n!/(C1!C2!Cn!1 2 n )个不同的置换.C1 C2 Cn第28页/共61页第二十九页，共61页。例例7.3.4对称对称(duchn)群共有群共有3个共轭类，个共轭类，即即 第29页/共61页第三十页，共61页。7.3.2 不动置换不动置换(zhhun)类类 定义定义定义定义7.3.3 7.3.3 设设设设GG是集合是集合是集合是集合S=1,2,nS=1,2,n上的一个置换上的一个置换上的一个置换上的一个置换(zhhun)(zhhun)群，群，群，群，k kS,S,GG，若，若，若，若(k)=k,(k)=k,即置换即置换即置换即置换(zhhun)(

43、zhhun)将将将将k k变为变为变为变为k,k,则称则称则称则称k k为置换为置换为置换为置换(zhhun)(zhhun)的不动点。的不动点。的不动点。的不动点。GG中中中中所有以所有以所有以所有以k k为不动点的全体置换为不动点的全体置换为不动点的全体置换为不动点的全体置换(zhhun)(zhhun)，构成，构成，构成，构成GG的一个子集，称为的一个子集，称为的一个子集，称为的一个子集，称为k k的不动置的不动置的不动置的不动置换换换换(zhhun)(zhhun)类类类类(k=1,2,n),(k=1,2,n),记为记为记为记为ZkZk。例例例例7.3.5 7.3.5 在在在在S3S3中，中

44、，中，中，Z1=e,(2,3),Z2=e,(1,3),Z3=e,(1,2).Z1=e,(2,3),Z2=e,(1,3),Z3=e,(1,2).第30页/共61页第三十一页，共61页。定理(dngl)7.3.2 置换群G中关于k的不动置换类Zk是G的一个子群。封闭性：kkk,k k.结合性：自然。有单位元：G的单位元属于Zk.有逆元：PZk,kk,则kk,P-1Zk.ZkG.P2 P1P1P2PP-1第31页/共61页第三十二页，共61页。7.3.3 等价等价(dngji)类类G=(1)(2)(3)(4),(12),(34),(12)(34).在G下，1变2，3变4，但1不变3。E1=E2=1,

45、2,E3=E4=3,4.2 个不同的等价类一般1,n上G将1,n分成(fn chn)若干等价类，满足等价类的3个条件.(a)自反性;(b)对称性;(c)传递性。第32页/共61页第三十三页，共61页。定义定义定义定义7.3.4 7.3.4 设设设设GG是集是集是集是集S=1,2,nS=1,2,n上的置换群上的置换群上的置换群上的置换群G=1,G=1,2,r.2,r.若存在集合中的元素若存在集合中的元素若存在集合中的元素若存在集合中的元素i,ji,j，满足，满足，满足，满足（i i）=j,=j,则则则则称称称称i i 与与与与j j 等价等价等价等价,记为记为记为记为i=ji=j；S S中与中与

46、中与中与i i等价的元素的全体等价的元素的全体等价的元素的全体等价的元素的全体(qunt)(qunt)记为记为记为记为EiEi，称为元，称为元，称为元，称为元素素素素i i的的的的“轨道轨道轨道轨道”.Ei”.Ei中的元素的个数称为轨道的长度中的元素的个数称为轨道的长度中的元素的个数称为轨道的长度中的元素的个数称为轨道的长度.元素元素元素元素i i与与与与j j的这种等价关系满足如下性质：的这种等价关系满足如下性质：的这种等价关系满足如下性质：的这种等价关系满足如下性质：反身性反身性反身性反身性:对称性：对称性：对称性：对称性：传递性传递性传递性传递性:因此，定义因此，定义因此，定义因此，定义

47、7.3.47.3.4中定义的等价关系就是离散数学中所中定义的等价关系就是离散数学中所中定义的等价关系就是离散数学中所中定义的等价关系就是离散数学中所提到的等价关系，而每个提到的等价关系，而每个提到的等价关系，而每个提到的等价关系，而每个EiEi就是相应的等价类。就是相应的等价类。就是相应的等价类。就是相应的等价类。第33页/共61页第三十四页，共61页。定理定理7.3.3 设设G是是1,n上的一个置换群，上的一个置换群，Ek是是1,n在在G的作用下包含的作用下包含k的等价的等价(dngji)类，类，Zk是是k不动置换类。有不动置换类。有|Ek|Zk|=|G|.第34页/共61页第三十五页，共6

48、1页。定理定理定理定理7.3.4 7.3.4 设设设设GG是是是是n n元集元集元集元集S=1,2,nS=1,2,n上的置换群上的置换群上的置换群上的置换群,G=1,2,n,G=1,2,n,把每个把每个把每个把每个ii都表示成不相杂的轮都表示成不相杂的轮都表示成不相杂的轮都表示成不相杂的轮换的乘积，令换的乘积，令换的乘积，令换的乘积，令k(i)k(i)表示置换表示置换表示置换表示置换ii中中中中k k阶轮换的个数阶轮换的个数阶轮换的个数阶轮换的个数,则则则则GG在在在在S S上诱导上诱导上诱导上诱导(yudo)(yudo)出的等价关系将出的等价关系将出的等价关系将出的等价关系将S S划分为划分

49、为划分为划分为不同等价类的个数为不同等价类的个数为不同等价类的个数为不同等价类的个数为 L=1(1)+1(2)+1(r)/|G|L=1(1)+1(2)+1(r)/|G|(7.3.1)(7.3.1)其中其中其中其中1()1()为置换为置换为置换为置换 中的不动点中的不动点中的不动点中的不动点(即即即即1 1阶轮换阶轮换阶轮换阶轮换)的个的个的个的个数数数数.第35页/共61页第三十六页，共61页。证明证明 按两种方法计算按两种方法计算S在在G中中的所有置换作用下不动点的总的所有置换作用下不动点的总个数个数N.（1）按置换逐个计算）按置换逐个计算:（2）按）按S中的每一个元素计中的每一个元素计算算

50、:两种方法所求结果应该一两种方法所求结果应该一致致,即即 (7.3.2)由假设由假设S可分解可分解L个不同个不同(b tn)的等价类，设为。的等价类，设为。第36页/共61页第三十七页，共61页。而且而且(r qi)(r qi)，若，若 (定理定理7.3.3)7.3.3)从而有从而有 代入式代入式(7.3.2)(7.3.2)整理即得整理即得(7.3.1)(7.3.1)式成立。式成立。第37页/共61页第三十八页，共61页。例如(lr)，G=e,(12),(34),(12)(34).1(a1)=4,1(a2)=2,1(a3)=2,1(a4)=0.l=4+2+2+0/4=2.以本例列表分析：1 2