《组合数学Pólya定理习题》由会员分享，可在线阅读，更多相关《组合数学Pólya定理习题（19页珍藏版）》请在金锄头文库上搜索。
1、第四章习题 1.试证(4-2-2)对应关系是同构。解 2.试证对于有限群G的任一元素a , 存在一 整数r , 使得a =e. 而且r必能整除g，g是群G的阶。解 3.试证下列函数对于运算fg=f(g(x)是一 个群。 f1(x)=x, f2(x)=, f3(x)=1-x, f4(x)=, f5(x)=, f6(x)=. 解1x1 1xx1x x x1rDate组合数学 4.一正立方体的六个面用g,r,b,y四种颜色 涂染，求其中两个面用色g,两个面用色y, 其余一面用b,一面用r的方案数。 解 5.对一正六面体的八个顶点，用y和r两种 颜色染色，使其中有5个顶点用色y,其余3 个顶点用色r,
2、求其方案数。 解 6.由b、r、g三种颜色的5颗珠子镶成的圆 环，共有几种不同的方案?解Date组合数学 7.一个圆圈上有n个珠，用n种颜色对这n 个珠子着色，要求颜色数目不少于n的方 案数。解 8.若已给两个r色的球，两个b色的球，用 它装在正六面体的顶点，试问有多少不 同的方案?解 9.试说明S5群的不同格式及其个数。解 10.图4-1-1用两种颜色着色的问题，若考 虑互换颜色使之一致的方案属同一类， 问有多少不同的图象？解Date组合数学 11.在正四面体的每个面上都任意引一条高，有 多少方案？解 12.一幅正方形的肖像与一个立方体的面一样大 ，6副相同的肖像贴在立方体的6个面上有多少
3、种贴法？解 13.凸多面体中与一个顶点相关的各面角之和与 2的差称为该顶点的欠角，证明凸多面体各顶 点欠角之和为4.解 14.足球由正5边形与正6边形相嵌而成。 (a)一个足球由多少块正5边形与正6边形组成？ (b)把一个足球所有的正6边形都着以黑色，正5 边形则着以其它各色，每个5边形的着色都不 同，有多少种方案？解Date组合数学 15.(a)本质上有多少种确实是2个输入端 的布尔电路？写出其布尔表达式。 (b)本质上有多少种确实是3个输入端 的布尔电路？解 16.用8个相同的骰子垛成一个正6面体， 有多少方案？解 17.正六面体的6个面和8个顶点分别用红 、蓝两种颜色的珠子嵌入。试问有多
4、少 种不同的方案数?(旋转使之一致的方案看 作是相同的).解Date组合数学习题解答 1.证：设G=a1,a2,an,指定G中任一元 ai, 任意ajG，Pi：aj ajai ，则Pi是G上 的一个置换，即以G为目标集。 Pi=( )， G的右正则表示f：ai( )=Pi。f是单 射：aiaj，则PiPj f(aiaj) = ( ) =( )( )=f(ai)f(aj) 证毕。 题a1 a2 ana1ai a2ai anaiai aaia1 a2 ana1(aiaj) a2(aiaj) an(aiaj)a1 a2 ana1ai a2ai anaia1 a2 an(a1ai)aj (a2ai)a
5、j (anai)ajDate组合数学 2.证：设|G|=g,则a,a ,a ,a ,a 中必有相 同元。a = a , 1klg+1 a =e. 1l-kg 对于给定的a，存在最小的正 整数r,a =e .于是 H=a ,a ,a (=e)是G的 子群，若HG,则存在a1不属于H, 显然 ，HHa1=,|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.证毕。题2 3 g g+1k ll-kr 2 r. . . . . . . .Date组合数学 3.证：(a)封闭性
6、：f1fi=f1(fi(x)=fi(x); f2f3=f2(f3(x)=f2(1-x)=1/(1-x)=f4(x); 同理一一列举可得任意fi都属于G; (b)结合律成立：运算相当于把前面的计 算结果带入到后面的函数中，对于该数 学运算，运算的先后顺序与结果无关。 结合律成立。 (c)存在单位元：e=f1; (d)存在逆元素： f1=e; f2f2=e; f3f3=e; f4f5=f5f4=e; f6f6=e; 满足群的条件，得证。题Date组合数学 4.解：正6面体的转动群用面的置换表示 ： 面心-面心 90 (1) (4) 6个 180 (1) (2) 3个 顶点-顶点 120 (3) 8
7、 个 棱中-棱中 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其中g y br的系数为 C(6,2)C(4,2)C(2,1)+3C(2,1)C(2,1)/24=8 题。22 22366 2 4 4 4 4 2 2 2 2 3 2 2 2 2 2 23 3 3 3 22 2Date组合数学 5.解：相当于4.7节中例2中求b r 的系数 ，为C(8,5)+8C(2,1)/24=3 题 6.解：正
8、5边形的运动群 题 绕心转 72 (5) 2个 144 (5) 2个 翻转 180 (1)(2) 5个 不动 (1) 1个 不同方案数为m=(3 +43 +53 )/10=39 7.解：使重合的运动包括绕中心旋转和绕 水平对称轴翻转共产生2n个置换群。5 3。1 1255 1 3Date组合数学 (续前)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 +
9、g +b ) /24 其中r g b 的系数为 C(8,2)C(6,2)+9C(4,2)C(2,1)/24=22题8 4 4 4 2 2 2 2 42 3 3 3 22 2 4Date组合数学 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个置换
10、； (2) (3) 共轭类有5!/(23)=20个置换； (5) 共轭类有5!/5=24个置换； 共有不同格式7种，如上所示。题53 1 1 222 11 11 11Date组合数学 10.解：类似讲义4.4例2求： (1)不换色 不动：p1=(1)(2)(3)(4)(5)(6)(7)(8)(9)(13)(14)(15)(16) 逆时针转90 :p2=(1)(2)(3456)(789 10)(11 12)(13 14 15 16)顺时针转90 :p3=(1)(2)(6543)(10 987)(11 12)(16 15 14 13)转180 :p4=(1)(2)(35)(46)(79)(8 10
11、)(11 12)(13 15)(14 16)(2)换色 不动：p5=(12)(37)(48)(59)(6 10)(11 12)(13 14)(15 16) 逆时针转90 :p6=(12)(385 10)(6749)(11)(12)(16 15 14 13)顺时针转90 :p7=(12)(10 583)(9476)(11)(12)(13 14 15 16)转180 :p8=(12)(39)(4 10)(57)(68)(11 12)(13)(14)(15)(16) (16+2+2+4+0+2+2+4)/8=4(种方案) 题。 。 。 。 。Date组合数学 11.解：除了绕顶点-对面的中心轴旋转均
12、 不会产生不变的图象外, 绕其他轴的旋转 相当于正4面体的面3着色。参照讲义4.6 例3可得不同的方案数为 M=3 +083 +33 /12=9题 12.解：除了绕面心面心轴旋转任何度 数均不会产生不变的图象外，绕其他轴 的旋转都相当于正六面体的面4着色。参 照讲义4.6例4可得不同的方案数为 M=4 +064 +034 +84 +64 /24=192 题4 2 26 3 4 2 3Date组合数学 13.证：设V,S,E分别为顶点集，面集，边 (棱)集。由欧拉定理 |V|+|S|E|=2. 设aij为与顶点vi，面Sj为相关的面角，ej为Sj的的边数，给定Sj则aij=(ej2) 欠角和为(2aij)=2 aij =2|V| aij=2|V|(ej2) =2|V|ej+2|S|=2|V|+2|S|2|E|=4 题SjSSjSSjSvjVSjSvjVSjSvjVvjVvjVDate组合数学 14.
