组合数学第六章-精简版

1、第六章Plya定理2022/9/1715-1Plya定理是1933年匈牙利数学家Plya以群论为理论基础、结合母函数方法建立起来的一个定理，它是组合数学中解决计数问题最重要的工具之一。6.1群的概念2022/9/1715-2给定非空集合G及G上的二元运算“”，若满足以下四个条件：封闭性，即对任意a,bG，有abG；结合律成立，即对任意a,b,cG，有(ab)c=a(bc)存在幺元e，即存在eG，使对任意aG，都有ea=ae=aG中每个元都存在逆元，即对任意aG，都存在bG，使得ab=ba=e(元素b称为a的逆元，记为a-1，即b=a-1),则称G关于运算“”作成一个群，或称G,是一个群，简称G

2、是一个群。群的说明2022/9/1715-3群G，中的运算也称为乘法，a,bG，ab可简记为ab;若G为有限集，则称G为有限群，G称为有限群G的阶；若运算满足交换律，即任意的a,bG,有ab=ba，则称G为交换群或Abel群。因群中结合律成立，(ab)c或a(bc)可记为abc。类似地,a1a2an表示在不改变元素的顺序条件下，以任意方式结合的n个元素的乘积。例12022/9/1715-4Z，+是一个群，其中Z为整数集，+为普通加法,称此群为整数加群。证明：因整数加整数仍为整数，故封闭性成立。因普通加法满足结合律，故Z中结合律成立。数0是幺元。这是因对任意的mZ，有0+m=m+0=m。对任意m

3、Z，有-mZ，使(-m)+m=m+(-m)=0，故m在Z中有逆元-m。所以Z,+是一个群。例22022/9/1715-5设Q*为非零有理数构成的集合，为普通乘法，则Q*,是一个群。证明：因非零有理数乘以非零有理数仍为非零有理数，故封闭性成立。因普通乘法满足结合律，故Q*中结合律成立。数1是幺元。这是因对任意的aQ*,有1a=a1=a对任意的aQ*，有1/aQ*，使1/aa=a1/a=1,故1/a是a的逆元。所以Q*，是一个群。例32022/9/1715-6设Zn=0,1,，n-1,在Zn上定义模n的加法+n如下：对任意的a,bZn，a+nb=(a+b)(mod n)，其中(a+b)(mod n

4、)表示(a+b)除以n的余数。显然Zn对+n封闭；可证结合律成立；0是幺元；0-1=0；a-1=n-a,a=1,2,n-1；故Zn,+n是一个群。例32022/9/1715-7设Mn(R)表示所有n阶实可逆矩阵构成的集合，“” 为矩阵的乘法。可证Mn(R),是一个群，E(单位矩阵)是幺元，AMn(R)的逆元为A的逆矩阵A-1。设G=1,-1,i,-i,其中i=,对普通乘法“”，易证G，是一个群。幺元为1，1的逆元为1，-1的逆元为-1，i与-i互为逆元。定理6.12022/9/1715-8设G是一个群，e为其幺元。e-1=e。G中幺元惟一，每个元的逆元惟一。G中消去律成立，即对任意a,b,cG

5、，若ab=ac或ba=ca，则必有b=c。a,bG,有(ab)-1=b-1a-1。幂2022/9/1715-9设G是一个群，e为其幺元，对任意aG，n为正整数，定义a=e；an=an-1a；a-n=(a-1)n。定理6.2：设G是一个群，aG，对任意的整数m,n有aman=am+n,(am)n=amn。子群2022/9/1715-10设G，是一个群，H是G的非空子集，对G中同一运算“”，若H，也是一个群，则称H，是G，的子群，简称H是G的子群。对任意的群G，G本身以及e(e为G的幺元)均为G的子群，称它们为平凡子群。如设Z、Q与R分别为整数集合、有理数集合及实数集合，+为普通加法，则Z，+与Q

6、，+均为R，+的子群。设H是群G的子群，由幺元及逆元的惟一性，可推知H与G的幺元是一致的，H中的元在H中的逆元与在G中的逆元也是一致的。定理6.32022/9/1715-11设是一个群，H是G的一个非空子集，则H是G的证明设H是G的子群，则由定义知：1)、2)成立；设H满足条件1)、2)，则需证明如下四点：1)、H是非空的子集：已知；2)、封闭性：显然(由条件1可得)；3)、逆元存在：显然(由条件2可得)；4)、幺元存在：由于H，所以有aH，由2)知：a-1H，由1)有：aa-1H，eGaa-1a-1aH，所以eG是H的幺元。由1)、2)、3)、4)知：是的子群。子群的充要条件是：对a，bH，有abH；对aH，有a-1H。例42022/9/1715-12对整数加群Z，+，令E=2mmZ，证明E，+是Z，+的子群。证明：显然E是Z的非空子集；对2m,2nE(m,nZ)，有(2m+2n)=2(m+n)E对2mE(mZ)，有(2m)-1=-2m=2(-m)E所以E，+是Z，+的子群。定理6.42022/9/1715-13设是一个群，H是G的一个有限非空子集，证明由定理6.3，只需证明对aH,有a-1H即可。事实上，由H的封闭性可知a,a2,a3,均为H的元。又H有限，故a,a2,中必有相同者，即存在正整数mn，使得am=an am-nan=ean其