资源描述：
《《组合数学》教案6章(波利亚定理)》由会员上传分享，免费在线阅读，更多相关内容在工程资料-天天文库。
1、第六章Polya《波利亚)定理1.群论基础2.置换群及其应用3・Burnside引理及其在染色问题中的应用4.P61ya定理及其在染色问题中的应用5.母函数型的P61ya定理及其应用(分类统计)6.1群论基础普通代数：计算对象为数，运算方式多为加、减、乘、除。扩展：计算对象为一般的集合元素，运算方式也可以是多种多样。例如矩阵运算、集合的并、交、差运算等。抽象代数：应用：代数、计数、通信编码、信息与网络安全等。§6.1.1群的概念【定义6.1.1］给定非空集合G及定义在G上的二元运算“•”,若满足以下四个条件，则称集合G在运算“•”下构成一个群，简称G为一个群：(1)封闭性：a
2、,beG,则abeG；(2)结合律：(ab)c=a(bc)；(3)单位元：存在ewG,对任意awG,有a・e=e・a=a；(4)逆元素：对任意awG,存在bwG,使得a・b=b・a=e,称b为a的逆元素，记为a】o群的运算符“•”可略去,即ab=ab・群的运算不要求满足交换律。否则称为为交换群或Abel群。群的元素可以是有限个，叫作有限群;也可以是无限个，叫无限群。以
3、G
4、表示有限群中元素的个数，称为群的阶，那么当G为无限群时，可以认为
5、G
6、=oo0【例6・1・1】偶数集，整数集乙有理数集Q,实数集R,复数集C关于数的加法构成群，称为加法群。(证)(1)封闭性：(2)结合律：
7、(3)单位元：0(4)逆元：a~x=—ao但是，关于数的乘法，这些集都不构成群。因为在偶数集中关于普通乘法不存在单位元。而在Z、Q、R、C中，虽然关于普通乘法有单位元1,但数0没有逆元。【例6・1・2】不含零的有理数集Qp实数集&和复数集G关于数的乘法构成群。单位元：e=l；a的逆元：a"1=-oa【例6.1.31G={1,一1}关于乘法构成群单位元为e=l；(-1)7=—1。【例6.1.4】1的n次方根关于乘法构成n阶循环群。(1)n=l,Gi={e=l}(即方程x=l的解)(2)n=2,G2={1,—1}(即方程兀2=1的解)(3)n=3,G冷(即方程工Qi的解)(4)一
8、般情形：Gn={ak=elklnn&=0,1,…,兀_1;i-V-Hf}单位元：e=l设q='41=e2,ri"=cos^—+isin^—,则元素a«=/的逆元为a；Wq”—k。【例6.1.5]G={0,1,…,n—1}在模n(即modn)的情况下关于加法运算构成群，当n为素数时，q=G—{0}={1，2,…,n—1}关于乘法运算也构成群(此时G构成域)。在G中，单位元为0,元素aeG的逆元为一a或n—a。在G[中，单位元则为1,a的逆元为a封闭性：T^Ta=Ta+fieT结合律：显然，=(modn)o特殊元素的逆：I-1=1>("一I)"=一1或n—1。【例6丄6】所有矩阵
9、关于矩阵加法，所有非奇异(即可逆)n阶矩阵关于矩阵乘法都构成群。前者是可交换的，后者是不可交换群。【例6.1.71二维欧几里德空间的刚性旋转变换集合T={Ta}构成阿贝尔群。其中Ta>Tp的二元运算T^Ta定义为：先做笃，再对其结果做与。验证乙:/•cosasma「丿sinacos勺(3)单位元:7；对应矩阵为E=‘10、(4)逆元素：(笃尸仏【例6.1.81设G={/j=x,血=—x,f3=一9/
10、=19XX成=占，人=1一「一}，定义G上的二元运算，fi=I-xI-X饥(X)),则G构成群。(证)首先Gh®其次：(1)可以逐一验证f^fj=eG;⑵同样可以逐一验证：(
11、/i*A)=7k；(3)单位元为/i=x；(4)f4,去互为逆元，其他士的逆元是自身。验证：=/.(/,«)=/«z*/.=z(/1«)=z«fl*f3=fl(/3(X))=/2f-l=i--=Z»WxJXA*/5=/4(/5W)=1-y=1=x=1一兀【例6・1・9】设G=｛全部整数｝,a,bGG,定义a*b=a+b-2,则G关于运算法构成一个群。(证)(1)a*b=a+b—2eG；(2)(a*b)*c=(a*b)+c-2=(a+b-2)+c-2=a+(b+c—2)—2=a+(b*c)—2=a*(b*c)(1)单位兀为2：a^2=a+2—2=a=2+a—2=2*a(2)a
12、的逆元为一a+4=4—a：a*(4—a)=a+(4—a)—2=2=(4—a)+a—2=(4—a)*a(3)满足交换律：a*b=a+b—2=b+a—2=b*a由抽屉原理知,必存在整数m,k,满足lWmvkWn+1,使得§6.1.2群的性质【定理6.1.1］群具有以下性质(1)单位元e唯一；(2)逆元唯一;(3)满足消去律：即对亦b,ceG,若ab=ac,则b=c；若ba=ca,则仍有b=c；(4)a,beG，则=bW,更一般有(血…c)J=c“…方f(5)若G是有限群，则对任意aeG,必存在一个最小常数r
