组合数学+卢开澄版++答案第四章

4.1证明所有的循环群是ABEL群证明：循环群也是群，所以群的定义不用再证，只需证明对于任意a,bG,G是循环群，有a*bb*a成立，因为循环群中的元素可写成a=x形式m所以等式左边xm×xnxmn,等式右边xn?xm＝xmn，a*bb*a，即所有的循环群都是ABEL群。4.2若x是群G的一个元素，存在一最小的正整数m，使x=e，则称m为xm的阶，试证：C=｛e,x,x2,…,xm-1｝证：x是G的元素，G满足封闭性所以，xk是G中的元素C∈G再证C是群：1、x,ixj∈C,xi·x=jxi+j若i+j<=m-1,则xi+j∈C若i+j>m,那么xi+j=xm+k=xm·x=xkk∈CC满足封闭性。2、存在3、显然满足4、存在所以单位元e.结合性。逆元，设xa·x=e=xbmx=xbm-axa∈C,(x)a-1=x=xbm-a4.3设G是阶为设G是阶为n的有则此题要证kn首先考察下列n+1个元素n的有限群，限群，则G的所有元素的阶都不超过n.证明：a是G中的任意元素，a的阶素为k，aaaaa,,,,....n1234由群的运算的封闭性可知，这n+1个元素都属于G,，而G中仅有n个元素，所以由鸽巢原理可知，这n+1个元素中至少有两个元素是相同的，不妨设为aiaijaaaj（1jn）iiaaa单位元，即j=e，又由元素的阶数的定义可时=e，且k是满足kjn由群的性质3可知，是知，当ja为k阶元素上诉等式的最小正整数，由此可证k

4.4若G是阶为n的循环群，求群G的母元素的数目，即G的元素可表示a的幂：a,a2……..an解：设n=p1a1…….p，共n个素数的乘积，所以群G中每个元素都以用这akkk个素数来表示，而这些素数，根据欧拉定理，一共有Φ(n)=n(1-1/p1)………(1-1/pk)所以群G中母元素的数目为n(1-1/p1)………(1-1/pk)个.4.5证明循环群的子群也是循环群证明：设H是G=<a>的子群，若H=<e>,显然H是循环群，否则取H中最小的正方幂元a，下面证明am是H的生成元,易见amH，只要证明H中的任何元m素都可以表成am的整数次方，由除法可知存在q和r,使得l=qm+r,其中0rm-1,因此有a=alqm，因为a是H中最小的正方幂元，必有r=0,这就证明出rmal=amq{am}证明完毕。4.6若H是G的子群，4.7若H是G的子群,|H|=k,试证：|xH|=kx和y是G的元素，试证xHyH或为空，或xHyH其中xG.证明：∵H是G的子群，xG∴|xH|≤k如果|xH|<k,则必存在a,bH,使得xa=xb,因为且xG所以存在逆元xxa=xxb-1-1∴a=b∴|H|<k又∵|H|=k∴|xH|=k.4.8有限群G的阶为n，H是G的子群，则H的阶必除尽G的阶。答案：已知|G|=n,|H|<=|G|设G={a0,a1,a2.......an1}，H={b0,b1,b2......bn1}因为H是G的子群，所以在H中的一个(b)一定在G中对应一个am使得mr(bm)ram，bam，则rm一定是m的倍数，所以则H的阶必除尽G的阶。所以有rm4．9G是有限群，x是G的元素，则x的阶必除尽G的阶。

解：证：设|G|=g,则x,x,x,,x中必有相同元。设xx,11，klg23g1kl则xlke，1lkg。对于给定的x，存在最小的正整数r，使得xe。于是H{x,x2,x3,,xr}是G的r子群，aH若，则，显然，HH，HH2r。若HHG，则HGaaabHH2rg,r|g，否则，H(HH)。于是HHHG，babaar(k1)grg，|。证毕。4.10若x和y在群G作用下属于同一等价类，则x所属的等价类Ex，y所属的等价类Ey有|Ex|=|Ey|x和y在群G作用下属于同一等价类，所以P使x和y互相转变，即解：因为x和y在群G作用下存在置换1Ex=Ey={x,y}所以|Ex|=|Ey|。4．11有一个3х3的正方形棋盘,若用红,蓝色对这9个格进行染色,要求两个格,其余染蓝色,问有多少种着色方案着红色?解:对于一个3×3的正方形棋盘,要求两个格着红色,其余染蓝色,如下图所示.置换群:格式:(1),1个.(1)3(2)3,4个.(1)(4)2,2个.(1)(2)4,1个9p(x)=1/8×[(1+x)9+4(1+x)(1+x2)3+2(1+x)(1+x4)2+(1+x)(1+x2)4]x2的系数为1/8×[C(9,2)+4(C(3,2)+C(3,1))+C(4,1)]=(36+24+4)/8=8其中划横线为红色,其它为蓝色.共8种着色方案.4.12：试用Burnside引理解决n个人围一圆桌坐下的方案问题。解：NN-1112NN-12536…345………4………6……图一C1………图二C2…………2314N5N-16………………图NCN……N12N-1N-23………………图N!CN!如图：N个人围成一个圆桌的所有排列如上图所示。一共N!个。旋转360/i，i={n,n-1,n-2,……1}；得到n种置换当且仅当i=1的置换（即顺时针旋转360/1度：P1=(c1)(c2)……(cn!);）时有1阶循环存在（因为只要圆桌转动，所有圆排列中元素的绝对位置都发生了所以不可能有1阶循环存在）。不同的等价类个数就是不同的圆排列个数，根据Burnside引理，变化，所以一共有(n-1)!种排列。4.13对正六角形的6个顶点用5种颜色进行染色，试问有多少种不同的方案，旋转使之重合作为相同处理解：首先对每个顶点进行编号，分别为1，2，3，4，5，6，根据旋转的角度不6次，得到不同的旋转方式同，共可以旋转0度：a123456c(a)=611旋转旋转60度：a123456c(a)=112旋转120度：a135246c(a)=213旋转180度：a142536c(a)=314旋转240度：a153264c(a)=215旋转300度：a165432c(a)=161所以G=6，根据Polya定理，m=5，l1Gmc(a1)mc(a2)...mc(a)6155555516123262635故一共2635种涂色方案4.15对一个正六面体的8个顶点，用色y，其余3个顶点用色r，求其方案数。解：相当于4.7节中例2中求b5r3的系数，为[C(8,5)+8C(2,1)]/24=3用y和r两种颜色染色，使其中有5个顶点4.15对一个正六面体的8个顶点，用y和r两种颜色染色，其中五个顶点用色y，其余三个顶点用色r，求方案数？1解：C8C=35812244.16：用b，r，g这3种颜色的5颗珠子镶成的圆环，共有几种不同的方案。解:正5边形的运动群绕心转±72。(5)1±144。(5)12个2个5个1个翻转180。(1)(2)2不动(1)5不同方案数为m=(35+4·31+5·33)/10=394.16用b，r，g，这三种颜色的5颗珠子镶成的圆环，共有几种不同的方案？15243解：G：(1)(2)(3)(4)(5),(12345),(13524),(14253),(15432),(1)(25)(34),(2)(13)(45),(3)(24)(15),(4)(35)(12),(5)(14)(23).|G|=10.应用polya定理，不同的方案数为：1(354*315*33)=39104─17一个圆圈上有n个珠子,用n种颜色对这n个珠子着色,要求颜色数目不少于n的方案数是多少?解:使重合的运动包括绕中心旋转和绕水平对称轴翻转共产生2n个置换群.n个球用n种颜色着色共有n!种不同方案.因此,所求方案数为n!/2n.4.18若以给两个r色球，量个b色的球，用它装在正六面体的顶点，试问有多少种不同的方案。解：单位元素（1）（2）（3）（4）（5）（6）（7）（8），格式为（1）8.绕中轴旋转90。的置换非别为（1234）（5678），（4321）（8765）格式为（4）2，同格式的共轭类有6个。绕中轴旋转180。的置换非别为（13）（24）（57）（68），格式为（2），同类置换4有3个。绕斜对角线旋转180。的置换为（17）（26）（35）（48），格式为（2）同类置换4有3个。绕斜对角线旋转120。的置换为（136）（475）（8）（2），（631）（574）（2）（8），3）（1）同类置换有8个。依据Polya定理，不同方案数为M=（28+6×22+3×2+6×2+8×2）/24=23格式为（224444.18．若已给两个r色的球，两个b色的球，用它装在正六面体的顶点，试问有多少种不同的方案？解：由P191例4-14知，六面体顶点的置换群中有一个(1)，六个(4)2，九8个(2)4，八个(3)(1)2，本题相当于用2个顶点涂r色，2个顶点涂b色，4个顶2w色，利用母函数形式的polya定理知总的方案数为点涂P1(rbw)6(r4bw4)29(r2bw2)48(rbw)2(r3bw3)2423824其中r2b2w4的系数即为所求，系数为22，总的所求方案数为22种。S4．19试说明群的不同格式及其个数。5解：5的拆分共有：00005,00014,00023,00113,00122,01112,11111共七种，则可得S群的７种不同格式如下：5(1)5共轭类有5!/5!=1个置换；(1)3(2)2共轭类有5!/(3!2)=10个置换；(1)1(2)2共轭类有5!/(2!2)=15个置换；(1)2(3)1共轭类有5!/(2!3)=20个置换；(1)1(4)1共轭类有5!/4=30个置换；(2)1(3)1共轭类有5!/(2·3)=20个置换；(5)1共轭类有5!/5=24个置换；4.19试说明S5群的不同格式及其个数。解：5的拆分有：00005,00014,00023,00113,00122,01112,11111共七种，则(5)1共轭类有5!/5=24个置换；(1)1(4)1共轭类有5!/4=30个置换；(2)1(3)1共轭类有5!/(2·3)=20个置换；(1)2(3)1共轭类有(1)1(2)2共轭类有5!/(2!2)=15个置换；(1)3(2)1共轭类有5!/(3!2)=10个置换；5!/(2!3)=20个置换；(1)5共轭类有5!/5!=1个置换；所以，共有不同格式7种，其总个数为119。4.20如图4-5一个方格平均分成四个部分有两种颜色着色的问题，若考虑呼唤颜色使之一致的方案属于同一类，问有多少种不同的图像？答案：(1)不换色:不动：p1=(1)(2)(3)(4)(5)(6)……(13)(14)(15)(16)逆时针转90度:p2=(1)(2)(3456)(78910)(1112)(13141516)顺时针转90度:p3=(1)(2)(6543)(10987)(1112)(16151413)转180度：(1)(2)(35)(46)(79)(810)(1112)(1315)(1416)(2)换色:不动：p5:=(12)(37)(48)(59)(610)(1112)(1315)(1416)逆时针转90度:p6=(12)(38510)(6749)(11)(12)(16151413)顺时针转90度：p7=(12)(10583)(9476)(11)(12)(13141516)转180度:p8=(12)(39)(410)(57)(68)(1112)(13)(14)(15)(16)总方案数为（12+2+2+4+0+2+2+4）/8=44.20图4-5用两种颜色着色问题，若考虑互换颜色使之一致的方案属于同一类，问有多少种不同的图象？答：有4种分别是4.21在正四面体的每个面上都任意引一条高,有多少种方案.解：问题相当于在4个面上用3种颜色着色，求方案数。使4个面重合的旋转群G的元素为:(1)(2)(3)(4),(1)(234),(1)(432),(2)(134),(2)(431),(3)(124),(3)(421),(4)(123),(4)(321),(12)(34),(13)(24),(14)(23)所以不同的方案数共有13483233218172271512124.21在正四面体的每个面上都任意引一条高，有多少种？题解：除了绕顶点-对面的中心轴旋转均不会产生不变的图象外,绕其他轴的旋转相当于正4面体的面3着色。参照讲义4.6例3可得不同的方案数为M=[34+0·8·32+3·32]/12=94.22一幅正方形的肖像与一个立方体的面一样大，6幅相同的肖像贴在立方体的6个面上，有多少种贴法？题解：除了绕面心—面心轴旋转任何度数均不会产生不变的图象外，绕其他轴的旋转都相当于正六面体的面4着色。不同的方案数为M=[46+0·6·43+0·3·44+8·42+6·43]/24=1924.22一幅正方形的小巷与一个立方体的面一样大。6幅相同的肖像贴在立方体的6个面上，有多少种贴法？解：除了绕面心以面心轴旋转任何读书均不会产生不变的图像外，绕其他轴的旋转都相当于正六面体的面4着色。可得不同的方案数为M=460*6*430*3*448*426*43/241924.23凸多面体中与一个顶点相关的各面角之和与2的差称为该顶点的欠角。证明凸多面体各顶点欠角之和为4。证：设V，S，E分别为顶点集，面集，边集。由欧拉定理V+S-E=2。设a为与顶点v面s相关的面角，e为s的边数，给定s则ijijjjja(e2)ijjvva)(2a)2jijijvvssvvjvvssjjjj=2V-aijvvssjj=2V-(e2)=2V-e+2Sjjssjssj=2V+2S-2E=4所以欠角和为4。4.24足球由正五边形和正六边形相嵌而成。(a)一个足球由多少块正五边形与正六边形组成？(b)把一个足球所有的正六边形都着以黑色，正五边形则着以其它各色，每个五边形的着色都不同，有多少种方案？解：（a）足球是多面体，满足欧拉公式F－E＋V＝2，其中F,E,V分别表示面,棱,顶点的个数。设足球表面正五边形和正六边形的面各有x个和y个，那么，面数F＝x＋y；棱数E＝(5x+6y)/2；顶点数V＝(5x+6y)/3。由欧拉公式，x＋y－(5x+6y)/2＋(5x+6y)/3＝2，解得x＝12。由于每一个六边形的六条边都与其它的三个六边形的三条边和三个五边形的三条边连接；每一个五边形的五条边都与其它的五个六边形的五条边连接。所以，五边形的个数x=3y/5。之前求得x=12，所以y=20。(b)一个顶点通过一个转动可与任一顶点重合，故转动群的阶为60。因为5边形着色均不同，重合的方式只有1种，所以除不变置换的任意旋转都不会产生不变图象，12个5边形着不同颜色共12!种方案。所以共有12!/60=7983360种方案。4.25．若G和G'是两个群GG'{(g,g')gG,g'G'},(g,g')(g,g')(gg,g'g'),11221212GG'的单位元素是(e,e'),试证GG'成群。证明：要证是群，即证GG满足群的四个性质：GGb(g,g)其（1）封闭性：若a,bGG,设a(g,g)其中gG,gG，xxxxyy，ab(gg,gg)由于G,G是群，所以中gG,gGyyxyxy，由定义知，故满足封闭性。ggG,ggGabGGxyxy（2）结合律：对于任意的a,b,cGG，a(g,g),b(g,g),c(g,g)，xxyyzz由于G,G是群，本身满足结合律，所以满足结合律。GG（3）存在单位元素，题中已给出。（4）存在逆元：对GG的任意元素a,a(g,g)，其中gG,gG，存xxxx在b，b(g1,g1)，显然bGG，ab(e,e)，所以存在逆元。xx综上所述：GG是群。4.25若G和G'是两个群(g,g')|gG,g'G'},G*G'{(g,g')(g,g')(gg,g'g').G*G'的单位元是(,')ee，证明11221212G*G'是群。证明：封闭性：设(g,g')，(g,g')G*G'，1122gg'{(,)|gG,g'G'},G*G'对于(g,g')，ggGGgg')，ggGG',,',同理(,''11112222ggg'gGG和G'是两个群，则'G',1212gg')(g,g')(gg,g'g')，封闭性成立。(,11221212结合性：若(g,g')，(g,g')，(g,g')G*G'112233（(g,g')(g,g')）(g,g')=(gg,g'g')(g,g')=(ggg,g'g'g')112233121233123123(g,g')((g,g')(g,g'))=(g,g')(gg,g'g')=(ggg,g'g'g')112233112323123123(ggg,g'g'g')=(ggg,g'g'g')123123123123即（(g,g')(g,g')）(g,g')=(g,g')((g,g')(g,g'))31结合律成立。1223112233ee单位元：G*G'的单位元是(,')逆元素：设，(g,g')，(g,g')G*G'1122若(g,g')(g,g'1gg')是(g,g')的逆元素。2ee)=(,')则(,212211gg')(g,g')(gg,g'g'(,ee)=(,')11221212gg'{(,)|gG,g'G'},G*G'gg,,eG12ggegg1，同理g'g，G是群'1122121(g,g')的逆元素为(g1,g'1)，逆元素存在。1111

综上，G*'是群。G4.26若G是关于X=｛x1,x2,,xn｝的置换群，G×G’的每一对元素证G×G’是关于X∪X’的置换群。G’是关于X’=｛x’1,x’2,,x’m｝的置换群，对于证：1、封闭性G×G’是群（g,g’）(v)1∈G×G’（g,g’）(v)2∈G×G’（g,g’）(v)1·（g,g’）(v)2=g(v)1·g’(v)2若v1、v2∈X，或v1、v2∈X’显然成立。或v1∈X，v2∈X’因为G是置换群，G’是置换群，g’(v)=xl∈G’x这一置换，可在X’中找到一个相应的置换与之对应若g(v)1∈Xg’(v)2∈X’那么，g(v1)=xk∈G那么，2对应于k那么n,m若相等，若m≠n,假设n>mg(v)1是G中一显然成立。个置换g’(v)2是G’中一对于g(v)1来说，乘以一个g’(v),由于g’(v)一个循环中元素个数最多不会超过22个置换g(v)1相当于，对于g’(v2),可在G中找到对应的。所以，g(v)1·g(v)2∈G此时，若m>n,g(v),g’(v)2∈X