搜索
2020/1/21组合数学第四章习题•1.试证(4-2-2)对应关系是同构。解•2.试证对于有限群G的任一元素a,存在一整数r,使得a=e.而且r必能整除g，g是群G的阶。解•3.试证下列函数对于运算f·g=f(g(x))是一个群。f1(x)=x,f2(x)=—,f3(x)=1-x,f4(x)=——,f5(x)=——,f6(x)=——.解1x11－xx－1xxx－1r2020/1/21组合数学•4.一正立方体的六个面用g,r,b,y四种颜色涂染，求其中两个面用色g,两个面用色y,其余一面用b,一面用r的方案数。解•5.对一正六面体的八个顶点，用y和r两种颜色染色，使其中有5个顶点用色y,其余3个顶点用色r,求其方案数。解•6.由b、r、g三种颜色的5颗珠子镶成的圆环，共有几种不同的方案?解2020/1/21组合数学•7.一个圆圈上有n个珠，用n种颜色对这n个珠子着色，要求颜色数目不少于n的方案数。解•8.若已给两个r色的球，两个b色的球，用它装在正六面体的顶点，试问有多少不同的方案?解•9.试说明S5群的不同格式及其个数。解•10.图4-1-1用两种颜色着色的问题，若考虑互换颜色使之一致的方案属同一类，问有多少不同的图象？解2020/1/21组合数学•11.在正四面体的每个面上都任意引一条高，有多少方案？解•12.一幅正方形的肖像与一个立方体的面一样大，6副相同的肖像贴在立方体的6个面上有多少种贴法？解•13.凸多面体中与一个顶点相关的各面角之和与2π的差称为该顶点的欠角，证明凸多面体各顶点欠角之和为4π.解•14.足球由正5边形与正6边形相嵌而成。(a)一个足球由多少块正5边形与正6边形组成？(b)把一个足球所有的正6边形都着以黑色，正5边形则着以其它各色，每个5边形的着色都不同，有多少种方案？解2020/1/21组合数学•15.(a)本质上有多少种确实是2个输入端的布尔电路？写出其布尔表达式。(b)本质上有多少种确实是3个输入端的布尔电路？解•16.用8个相同的骰子垛成一个正6面体，有多少方案？解•17.正六面体的6个面和8个顶点分别用红、蓝两种颜色的珠子嵌入。试问有多少种不同的方案数?(旋转使之一致的方案看作是相同的).解2020/1/21组合数学习题解答•1.证：设G={a1,a2,…,an},指定G中任一元ai,任意aj∈G，Pi：aj→ajai，则Pi是G上的一个置换，即以G为目标集。Pi=()，G的右正则表示f：ai→()=Pi。f是单射：ai≠aj，则Pi≠Pjf(aiaj)=()=()()=f(ai)f(aj)证毕。题a1a2…ana1aia2ai…anaiaiaaia1a2…ana1(aiaj)a2(aiaj)…an(aiaj)a1a2…ana1aia2ai…anaia1a2…an(a1ai)aj(a2ai)aj…(anai)aj2020/1/21组合数学•2.证：设|G|=g,则a,a,a,…,a,a中必有相同元。a=a,1≤k＜l≤g+1a=e.1≤l-k≤g对于给定的a，存在最小的正整数r,a=e.于是H={a,a,…,a(=e)}是G的子群，若H≠G,则存在a1不属于H,显然，H∩Ha1=φ,|H+Ha1|=2r若H+Ha1=G,则2r=g,r|g否则存在a2不属于H+Ha1,Ha2∩(H+Ha1)=φ于是H+Ha1+Ha2+…+Hak=G,r(k+1)=g,r|g.证毕。题23gg+1kll-kr2r........2020/1/21组合数学•3.证：(a)封闭性：f1·fi=f1(fi(x))=fi(x);f2·f3=f2(f3(x))=f2(1-x)=1/(1-x)=f4(x);同理一一列举可得任意fi都属于G;(b)结合律成立：运算相当于把前面的计算结果带入到后面的函数中，对于该数学运算，运算的先后顺序与结果无关。结合律成立。(c)存在单位元：e=f1;(d)存在逆元素：f1=e;f2·f2=e;f3·f3=e;f4·f5=f5·f4=e;f6·f6=e;满足群的条件，得证。题2020/1/21组合数学•4.解：正6面体的转动群用面的置换表示：面心-面心±90(1)(4)6个180(1)(2)3个顶点-顶点±120(3)8个棱中-棱中180(2)6个不动(1)1个P=[(g+r+b+y)+6(g+r+b+y)(g+r+b+y)+6(g+r+b+y)+3(g+r+b+y)(g+r+b+y)+8(g+r+b+y)]/24其中gybr的系数为[C(6,2)C(4,2)C(2,1)+3C(2,1)C(2,1)]/24=8题。。。。2222366244442222322222233332222020/1/21组合数学•5.解：相当于4.7节中例2中求br的系数，为[C(8,5)+8C(2,1)]/24=3题•6.解：正5边形的运动群题绕心转±72(5)2个±144(5)2个翻转180(1)(2)5个不动(1)1个不同方案数为m=(3+4·3+5·3)/10=39•7.解：使重合的运动包括绕中心旋转和绕水平对称轴翻转共产生2n个置换群。53。。。11255132020/1/21组合数学•(续前)n个球用n种颜色着色共有n!种不同方案。因此，所求方案数为n!/2n.题•8.解：正六面体顶点的置换群见4.7例2，本题相当于用2个r,两个g,4个b色的球装在正六面体的8个顶点上。P=[(r+g+b)+6(r+g+b)+9(r+g+b)+8(r+g+b)(r+g+b)]/24其中rgb的系数为[C(8,2)C(6,2)+9C(4,2)C(2,1)]/24=22题844422224233322242020/1/21组合数学•9.解：5的拆分共有：00005,00014,00023,00113,00122,01112,11111共七种，根据讲义4.4节定理1可得S5中：(1)共轭类有5!/5!=1个置换；(1)(2)共轭类有5!/(3!2)=10个置换；(1)(2)共轭类有5!/(2!2)=15个置换；(1)(3)共轭类有5!/(2!3)=20个置换；(1)(4)共轭类有5!/4=30个置换；(2)(3)共轭类有5!/(2·3)=20个置换；(5)共轭类有5!/5=24个置换；∴共有不同格式7种，如上所示。题53112221111112020/1/21组合数学•10.解：类似讲义4.4例2求：(1)不换色不动：p1=(1)(2)(3)(4)(5)(6)(7)(8)(9)…(13)(14)(15)(16)逆时针转90:p2=(1)(2)(3456)(78910)(1112)(13141516)顺时针转90:p3=(1)(2)(6543)(10987)(1112)(16151413)转180:p4=(1)(2)(35)(46)(79)(810)(1112)(1315)(1416)(2)换色不动：p5=(12)(37)(48)(59)(610)(1112)(1314)(1516)逆时针转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)•(16+2+2+4+0+2+2+4)/8=4(种方案)题。。。。。。2020/1/21组合数学•11.解：除了绕顶点-对面的中心轴旋转均不会产生不变的图象外,绕其他轴的旋转相当于正4面体的面3着色。参照讲义4.6例3可得不同的方案数为M=[3+0·8·3+3·3]/12=9题•12.解：除了绕面心—面心轴旋转任何度数均不会产生不变的图象外，绕其他轴的旋转都相当于正六面体的面4着色。参照讲义4.6例4可得不同的方案数为M=[4+0·6·4+0·3·4+8·4+6·4]/24=192题422634232020/1/21组合数学•13.证：设V,S,E分别为顶点集，面集，边(棱)集。由欧拉定理|V|+|S|－|E|=2.设aij为与顶点vi，面Sj为相关的面角，ej为Sj的的边数，给定Sj则∑aij=(ej－2)π欠角和为∑(2π－∑aij)=∑2π－∑∑aij=2|V|π－∑∑aij=2|V|π－∑(ej－2)π=2|V|π－∑ejπ+2|S|π=2|V|π+2|S|π－2|E|π=4π题Sj∈SSj∈SSj∈Svj∈VSj∈Svj∈VSj∈Svj∈Vvj∈Vvj∈V2020/1/21组合数学•14.解：5边形面心与体心连一直线从另一5边形面心穿出。该直线为对称轴。欠角=360–(108+2·120)=12720/12=60(个顶点)60·3/2=90(条棱)60/5=12(个5边形)60·2/6=20(个6边形)一个顶点通过一个转动可与任一顶点重合，重合的方式只有1种，故转动群的阶为60。因为5边形着色均不同，所以除不变置换的任意旋转都不会产生不变图象，12个5边形着不同颜色共12!种方案。所以共有12!/60=7983360种方案。题。。。。2020/1/21组合数学•15.解：S2:(1)题(1)(2)l=[2+2]/2=12其中包括0个输入端的2个，1个输入端的2个，故确实是2个输入端的布尔电路是8个。S3:(1)1个；(1)(3)2个；(1)(2)3个l=[2+2·2+3·2]/6=80，80－12=68，确实是3输入端的布尔电路本质上有68个。8468224200011011000110110001101100100111434212020/1/21组合数学•16.解：相当于正六面体每个角上放一个骰子。骰子按讲义4.6中关于正立方体的不同旋转均不会产生重合现象，共24种方案。因此本题相当于正六面体的顶点24着色。但绕顶点-顶点的对称轴旋转不会产生重合的图象。参照习题11可得不同的方案数为M=[24+6·24+3·24+0·8·24+6·24]/24=8011008题634232020/1/21组合数学•17.解：本题相当于把讲义4.6例4例5合并起来,8个顶点6个面共14个元素的置换群。面心-面心±90(1)(4)(4)6个180(1)(2)(2)3个顶点-顶点±120(3)(1)(3)8个棱中-棱中180(2)(2)6个不动(1)(1)1个[6·2+3·2+8·2+6·2+2]/24=776题。。。。2122242223468586714