第五章 Pólya计数理论
1. 计算（123）（234）（5）（14）（23）,并指出它的共轭类.
解：题中出现了5个不同的元素：分别是：1，2，3，4，5。即|Sn|＝5。
(123)(234)(5)(14)(23)?12345??12345??12345?
???23145????13425????43215?????????12345??12345????34125????43215?? ?????12345????21435?? ???(12)(34)(5)
（5）（12）（34）的置换的型为1122而Sn中属于1122型的元素个数为个其共轭类为
（5）（14）（23），（5）（13）（24），（1）（23）（45），（1）（24）（35）， （1）（25）（34），（2）（13）（45），（2）（14）（35），（2）（15）（34）， （3）（12）（45），（3）（14）（25），（3）（15）（24），（4）（12）（35）， （4）（13）（25），（4）（15）（24）
2. 设D是n元集合,G是D上的置换群.对于D的子集A和B,如果存在??G,
使得B?{?(a)|a?A},则称A与B是等价的.求G的等价类的个数.
1n?c1(ai)，其中c1(ai)表示在置换ai作用下保持不变解：根据Burnside引理l?Gi?15!?152!1!1122的元素个数，则有 c1(σI)=n;
设在σ的作用下，A的元素在B中的个数为i，则
c2(σ)=n－2i；
1若没有其他置换，则G诱出来的等价类个数为l=[n?(n?2i)]?n?i
23. 由0,1,6,8,9组成的n位数,如果把一个数调转过来读得到另一个数,则称这两
个数是相等的.例如,0168和8910,0890与0680是相等的.问不相等的n位数有多少个？
解：该题可理解为相当于n位数，0，1，6，8，9这5个数存在一定的置换关系
31
对于置换群G={g1,g2}
g1为不动点置换，型为1n；为5n；
n??n?g2置换：（1n）(2(n-1))(3(n-2))…(??2??2?) ????分为2种情况：
（1） n为奇数时12 ，但是只有中间的数字是0，1，8的时候，才可能调
转过来的时候是相同的，所以这里的剩下的中间数字只能是有3种。
即：个数为3×5n2n2n?12
n2（2） n为偶数时 2 ，个数为 5 该置换群的轮换指标为
1n122(5?5)?5 n为偶数时，等价类的个数l=221nn为奇数时，等价类的个数l=(5?3?52n?12n3n)
4. 现有8个人计划去访问3个城市,其中有3个人是一家,另外有2个人是一家.
如果一家人必须去同一个城市,问有多少种方案？写出它们的模式. 解：令D={d1,d2,…,d8}，其中，d1,d2,d3为一家，d4,d5为一家。R={c1,c2,c3},w(c1)=
α,w(c2)=β,w(c3)=γ.f:D→R是一种安排方案。根据题意，做D的一个5分划 {d1,d2,d3},{d4,d5},{d6},{d7},d8},
要求f在每块中的元素取值相同。对于{d1,d2,d3}，可以取α3＋β3＋γ3模式；对于{d4,d5 }，可以取α2＋β2＋γ2模式；对于{d6},{d7},{d8}，可以取α＋β＋γ模式.所以，总的模式为
（α3＋β3＋γ3）（α2＋β2＋γ2）（α＋β＋γ）3
5. 对正立方体6个面用红、蓝、绿3种颜色进行着色,问有多少种不同的方案？又问3种颜色各出现2次的着色方案有多少种？ 解：正立方体6个面的置换群G有24个元素，它们是：
（1） 不动的置换，型为16，有一个；
（2） 绕相对两面中心轴旋转90°，270°的置换，型为1241，有6个；旋
转180°的置换，型为1222，有3个； （3） 绕相对两顶点连线旋转120°，240°的置换，型为32，有8个； （4） 绕相对两边中点连线旋转180°的置换，型为23，有6个。 所以，该置换群的轮换指标为 PG（x1,x2,…,x6）=等价类的个数为
1622223(x1?6x1x4?3x1x2?8x3?6x2) 2432
l=PG(3,3,…,3)=
16(3?6?33?3?32?32?8?32?6?33)=57 24下面计算全部着色模式。这里，R={c1,c2,c3}，w(c1)=r，w(c2)=b，w(c3)=g，于是
F的全部模式表
1[(r?b?g)6?6(r?b?g)2(r4?b4?g4)?3(r?b?g)2(r2?b2?g2)224
33322223?8(r?b?g)?6(r?b?g)]其中，红色、蓝色、绿色各出现2次的方案数就是上述展开式中r2b2g2项的系数，即
16!3!(?3?2?6?)?6 242!2!2!1!1!1!6. 有一个3×3的正方形棋盘,若用红蓝两色对这9个方格进行着色,要求两个位
红色,其余为蓝色,问有多少种方案？ 解： 其置换群为：
不动置换：型为 19，1个
沿中间格子及其对角线方向做旋转的置换：型为1323，4个 旋转90°和240°时的置换：型为1142 ， 2个 旋转180°时的置换 型为1124， 1个
193234224P(x)=(1?x)?4(1?x)(1?x)?2(1?x)(1?x)?(1?x)(1?x)
8我们设定x为红色，1为蓝色，即转化为求x2的系数 （1） 对应于19，（1＋x）9中x2项系数为C(9,2)=36； （2） 对应于1323，4(1＋x)3(1+x2)3中x2项系数为：
4[C(3,2)C(3,0)+C(3,0)C(3,1)]=24；
（3） 对应于1142 2(1+x)(1+x4)2中x2项系数为0； （4） 对应于1124 (1+x)(1+x2)4中x2项系数为C(4,1)=4；
??1故x的系数为 (36?24?4)?8
82
7. 对正六角形的6个顶点用5种颜色进行着色.试问有多少种不同的方案,旋转
使之重合作为相同处理.
解：对该正六角形的6的顶点的置换群有12个，它们分别是：
(1) 不动点置换，型为16，有1个；
(2) 旋转60°和300°的置换，型为61，有2个；旋转120°和240°的置换， 型为32，有2个； 旋转180°的置换型为23有1个； (3) 绕对角连线旋转180°的置换 ，型为1222，有3个； (4) 绕对边中点连线旋转180°的置换，型为23，有3个。
33
所以，该置换群的轮换指标为
162223(x?2x?2x?3xx?3xPG（x1,x2,…,x6）=163122) 12下面计算全部着色模式。这里，R={c1,c2,c3,c4,c5}，不妨设w(c1)=r，w(c2)=b，w(c3)=g，w(c4)=p，w(c3)=y，于是 F的全部模式表
1[(r?b?g?p?y)6?2(r6?b6?g6?p6?y6)?2(r3?b3?g3?p3?y3)212?3(r2?b2?g2?p2?y2)(r2?b2?g2?p2?y2)2?3(r2?b2?g2?p2?y2)3]
其中，用这5种颜色着色的方案数就是上述展开式中r2bgpy, rb2gpy, rbg2py,rbgp2y, rbgpy2项的系数之和，即
16!(5?)?150 122!1!1!1!1!8. 在一个有7匹马的旋转木马上用n种颜色着色,问有多少种可供选择的方案？
（旋转木马只能转动不能翻转） 解： 设想另一个正7边形与不动的正7边形完全重合，并且顶点标记相同，那
360?么绕中心旋转i（1≤i≤7）角度，使得能够与不动的正7边形重合。它
7对应的置换是：71 共6个。故其轮换指标为 PG(x1,x2,…xn)=
17(x1?6x7) 717777计算全部着色模式为[(x1?x2?...?xn)7?6(x1?x2?...?xn)]
17!6!7!??C(7,n)??n<7时为 71!1!...[7?(n?1)]!(8?n)!n!(7?n)!
9. 一个圆圈上有n个珠子,用n种颜色对珠子着色,要求颜色数目不少于n的方
案数是多少? 解：（1）不动点置换有一个；
360?（2）绕中心旋转i（1≤i≤n）角度，使得能够与不动的环重合。它对应
n的置换是：n1 共(n－1)个；
（3）把n为奇数、偶数分两种情况分析： i)
n为奇数时：沿一颗珠子和其他剩余珠子的平分线绕180°，对应的置换是121n?12共
n个；
34
ii) n为偶数时：沿珠子平分线绕180°，对应的置换是2，共个。 故其轮换指标为
n?11n(x1?(n?1)xn?nx1x22)（n为奇数时）PG(x1,x2,…xn)= ； 2nn2n22nnn(x?(n?1)x?x22)（n为偶数时）PG(x1,x2,…xn)= ； 1n3n210. 骰子的6个面上分别标有1,2,…,6,问有多少种不同的骰子？ 解：下面有3种方法求解：
方法1 6个面分别标上不同的点数，相当于用6种不同的颜色对它着色，
并且每种颜色出现且只出现一次，共有6！种方案。但这种方案经过正立方体的旋转可能会发生重合，全部方案上的置换群G显然有24个元素。由于每个面的着色全不相同，只有恒等置换σI 保持6！种方案不变，即c1(σI)=6!，c1(p)=0（p≠σI）。由Burnside引理知 l?11?c1(?)=(6!?0???0)?30 G??G24方法2 在习题5中已求出关于正立方体6个面的置换群轮换指标，如果用m种颜色进行着色，则不同的着色方案数为
lm?1(m6?3?m4?12?m3?8?m2) 24严格的说，lm是至多用m种颜色着色的方案数。我们可以计算出l1=1,l2=10,l3=57,l4=240,l5=800,l6=2226。现令ni表示恰好用i种颜色着色的方案数，则由容斥原理知 n1=l1=1
?2?n2?l2???1??n1?8
???3??3??n3?l3??n??2?2??1??n1?30 ?????4??4??4????n4?l4??n?n??3?3?2?2??1??n1?68 ???????5??5??5??5??????n5?l5??n?n?n??4?4?3?3?2?2??1??n1?75 ???????? 35
