组合数学习题5（共5章）(3)

个顶点的3个面对应过3个中心的三角形，由此构成的6个顶点，8个面的几何图形。即可得到我们需要的正八面体的形状。 解：通过刚才我们的提示可以得到如下结论：可以把问题转换成对于正六面体的

顶点和面的着色问题，转换成为要求给这个正六面体着色：用红、蓝两色对6个面进行着色；用黄、绿两种颜色对8个顶点进行着色,试求其中4个面为红,2个面为蓝；黄和绿的顶点各4个的方案数.

对正六面体的6个面的置换群设为G，G的循环指数多项式为：

622232 P(G)=S1?6S1S4?3S1S2?6S2?8S3

设正六面体8个顶点的置换群为H，H的循环指数多项式为

82422P(H)=S1?6S4?9S2?8S1S3

P(G?H)=P(G)P(H)=

12324{ S16?6S12S4?3S12S2?6S2?8S32 }{S18?6S4?9S2?8S12S32} 2(24)所求的不同等价类数为

1[(r?b)6?6(r?b)2(r4?b4)?3(r?b)2(r2?b2)2?6(r2?b2)3?8(r3?b3)2] 24?1[(y?g)8?6(y4?g4)2?8(y?g)2(y3?g3)2?9(y2?g2)4] 24所得的r4b2y4g4的系数即为所求：

1?6!2!3!?1?8!2!2!2!4!????6?1?3(1?)?6???6??8()?9=2×7＝14 ?24?4!2!1!1！2!?1!?1!1!1!1!1!1!2!2!??24?4!4!? 所以符合题意的方案数为14种。

16. 用Pólya定理求多重集合M?{??a1,??a2,?,??an}的r圆排列数. 解：可转化为有r颗珠子的项链可以着n种颜色的方法数。

（1）不动点置换有1个；

38

360?i（1≤i≤r）角度，使得能够与不动的环重合。它对（2）绕中心旋转r应的置换是：r1 共(r－1)个； i)

（3）把r为奇数、偶数分两种情况分析：

r为奇数时：沿一颗珠子和其他剩余珠子的平分线绕180°，对应的置换是121r?12共r个；

r2ii) r为偶数时：沿珠子平分线绕180°，对应的置换是2，共个。

故其轮换指标为

r?11r(x1?(r?1)xr?rx1x22)（r为奇数时）PG(x1,x2,…xn)= ； 2rr21r =(n?(r?1)n?rn?n2rr?12)

1r =(n?(r?1)n?rn2rr?12)

2rrr(x?(r?1)x?x22)（r为偶数时）PG(x1,x2,…xn)= ； 1r3r22rr2(n?(r?1)n?n) =3r2r17. 求n个顶点的简单图有多少个？

解：简单图指的是过两个顶点没有多于一条的边，而且不存在圈的图形。问题相

当于对n个无标志顶点的完全图的(n?1)条边，用两种颜色进行着色，求不同方案数的问题。比如两种颜色x,y，令着上色y的边从图中消去，得到一

n个顶点的简单图。 例如3个顶点的无向图，有

G={(v1)(v2)(v3)，(v1v2v3)，(v3v2v1)，(v1)(v2v3)，(v2)(v1v3)，(v3)(v1v2)} P(x,y)=[(x?y)3?3(x?y)(x2?y2)?2(x3?y3)]

=x3+y3+xy2+x2y v1

v2 v3

从P(x,y)可知，对上图的三角形的边着色，其中3条边都用x着色的有1；同样

39

n216用x着色两条的、着色一条的、无一条着色的方案各为1（多项式各项的系数）。把用y着色的边消除得到以下的图形。

再看n=4的情况.令e1=(v1v2)，e2=(v2v3)，e3=(v3v4)，e4=(v4v1)，e5=(v1v3)，e6=(v2v4)，则{v1,v2,v3,v4}上的每个置换确定了{e1,e2,e3,e4,e5,e6}上的置换，后者构成边集合上的置换群G. G中有16型的置换1个，1222型的置换9个，32型的置换8个，2141型的置换6个.G的轮换指标为：

PG(x1,x2,…,x6)=

16222(x1?9x1x2?8x3?6x2x4) 24令R={x, y}，w(x)=r, w(y)=1则 PG(r+1,r2+1,…, r6+1)=

1[(r?1)6?9(r?1)2(r2?1)2?8(r3?1)2?6(r2?1)(r4?1)) 24 =r6+r5+2r4+3r3+2r2+r+1

故4个结点的简单图共有11个，如图所示：

40