《组合数学第四章Pólya定理习题》课件.ppt

组合数学 组合数学 * 组合数学 第四章习题 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)=——. 解 1 x 1 1－x x－1 x x x－1 r * 组合数学 4.一正立方体的六个面用g,r,b,y四种颜色涂染，求其中两个面用色g,两个面用色y,其余一面用b,一面用r的方案数。 解 5.对一正六面体的八个顶点，用y和r两种颜色染色，使其中有5个顶点用色y,其余3个顶点用色r,求其方案数。 解 6.由b、r、g三种颜色的5颗珠子镶成的圆环，共有几种不同的方案? 解 * 组合数学 7.一个圆圈上有n个珠，用n种颜色对这n个珠子着色，要求颜色数目不少于n的方案数。 解 8.若已给两个r色的球，两个b色的球，用它装在正六面体的顶点，试问有多少不同的方案? 解 9.试说明S5群的不同格式及其个数。解 10.图4-1-1用两种颜色着色的问题，若考虑互换颜色使之一致的方案属同一类，问有多少不同的图象？ 解 * 组合数学 11.在正四面体的每个面上都任意引一条高，有多少方案？ 解 12.一幅正方形的肖像与一个立方体的面一样大，6副相同的肖像贴在立方体的6个面上有多少种贴法？ 解 13.凸多面体中与一个顶点相关的各面角之和与2π的差称为该顶点的欠角，证明凸多面体各顶点欠角之和为4π. 解 14.足球由正5边形与正6边形相嵌而成。 (a)一个足球由多少块正5边形与正6边形组成？(b)把一个足球所有的正6边形都着以黑色，正5边形则着以其它各色，每个5边形的着色都不同，有多少种方案？ 解 * 组合数学 15.(a)本质上有多少种确实是2个输入端的布尔电路？写出其布尔表达式。 (b)本质上有多少种确实是3个输入端的布尔电路？ 解 16.用8个相同的骰子垛成一个正6面体，有多少方案？ 解 17.正六面体的6个面和8个顶点分别用红、蓝两种颜色的珠子嵌入。试问有多少种不同的方案数?(旋转使之一致的方案看作是相同的). 解 * 组合数学 习题解答 1.证：设G={a1,a2,…,an},指定G中任一元ai, 任意aj∈G，Pi：aj → ajai ，则Pi是G上的一个置换，即以G为目标集。　Pi=( 　 )， G的右正则表示f：ai→( )=Pi。f是单射：ai≠aj，则Pi≠Pj f(aiaj) = ( ) =( )( )=f(ai)f(aj) 证毕。 题 a1 a2 … an a1ai a2ai … anai ai aai a1 a2 … an a1(aiaj) a2(aiaj) … an(aiaj) a1 a2 … an a1ai a2ai … anai a1 a2 … an (a1ai)aj (a2ai)aj … (anai)aj * 组合数学 2.证：设|G|=g,则a,a ,a ,…,a ,a 中必有相同元。a = a , 1≤k＜l≤g+1 a =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. 证毕。 题 2 3 g g+1 k l l-k r 2 r . . . . . . . . * 组合数学 3.证：(a)封闭性：f1·fi=f1(fi(x))=fi(x); f