组合数学(27)

1、1第八章第八章 Polya计数法计数法14.3 Polya计数公式计数公式(一一) 本节课通过研究置换中的本节课通过研究置换中的循环结构循环结构, 使得不使得不等价是着色问题计算变是简单。等价是着色问题计算变是简单。 设设 f 是集合是集合X = 1,2,3,n的一个置换的一个置换, Df是是顶点集合为顶点集合为X并且弧集合为并且弧集合为Af = ( i, f(i) | i X 的有向图。将有向图的有向图。将有向图Df用图论中的标准表示方用图论中的标准表示方法记法记: Df = (X , Af ) 即用顶点集和边集的序偶即用顶点集和边集的序偶2表示。该有向图的边集是由弧构成表示。该有向图的边集

2、是由弧构成, 有向弧的起有向弧的起 点是点是i, 终点是通过置换得到的终点是通过置换得到的 f(i)，例如：，例如：7231458687654321: f置换是该有向图如右图所示该有向图如右图所示:我们能得到几个小的循我们能得到几个小的循环环: 16351;2872; 44;167243853 以以3,5,6,7,8为起点的循环已经包含在上述三个为起点的循环已经包含在上述三个 循环中循环中; 我们将这种小循环定义成我们将这种小循环定义成循环循环。每个循环用中括号加一有序数组表示：每个循环用中括号加一有序数组表示： 循循 环环表表 达达 式式(有向圈有向圈)163511 6 3 528722 8

3、 7 244;4 保持一个循环不变。在这个循环外的元素保持一个循环不变。在这个循环外的元素都作恒等置换，表示成下列置换：都作恒等置换，表示成下列置换：4 以上这种保持一个循环不变。这个循环以上这种保持一个循环不变。这个循环外余下的元素都作恒等置换，称这样的置换为外余下的元素都作恒等置换，称这样的置换为循环置换循环置换或者或者循环环循环环。如果循环置换中的元素。如果循环置换中的元素87654321876543214726543818765432178287314526876543215361 5是是k个，我们就称为个，我们就称为k-循环，如循环，如1 6 3 5是是4-循环循环 置换置换 f 的

4、划分的划分Df = 1 6 3 5,2 8 7 2,4那么，置换那么，置换 f 就可以按划分成循环环关于合成运就可以按划分成循环环关于合成运算的因式分解。算的因式分解。 这是因为置换中的每个元素仅仅属于因式这是因为置换中的每个元素仅仅属于因式分解的某个循环因子。分解的某个循环因子。4287216357231458687654321f6设设 f 是集合是集合X的任意置换，按上例推广为：的任意置换，按上例推广为： f =i1, i2, ., ip 。j1, j2, ., jq 。 。l1, l2, ., lr 其中集合其中集合X的各个元素只出现在某一个循环中。的各个元素只出现在某一个循环中。我们将

5、上式称为置换我们将上式称为置换f 的的循环因子分解循环因子分解，除循，除循环出现的次序外，环出现的次序外， f 的循环因子分解的唯一的。的循环因子分解的唯一的。例：正方形角点标以例：正方形角点标以1、2、3、4，在平面旋，在平面旋转和空间翻转可以得到转和空间翻转可以得到8个置换。个置换。71432 其中：其中：,432134241404cG;32144321;21434321;14324321;4321432134241404;12344321;34124321;41234321;2341432143218 对每个置换我们可以用下表描述因式分解对每个置换我们可以用下表描述因式分解置置 换换循环

6、的因式分解循环的因式分解1 。2 。3 。41 2 3 41 3 。2 41 4 3 21 。2 4 。31 3 。2 。41 2 。3 41 4 。2 32134241404349 由上表看出对与恒等置换由上表看出对与恒等置换的循环因子分解中，的循环因子分解中， 所有的的循环因子都是所有的的循环因子都是1-循环，这与恒等置循环，这与恒等置换保持所有元素不变这个事实相吻合。换保持所有元素不变这个事实相吻合。例：求例：求(10阶二面体群阶二面体群) 正五边形的顶点对称群中正五边形的顶点对称群中各置换的循环因子分解。各置换的循环因子分解。解：如右图所示，置换是解：如右图所示，置换是由平面由平面5个

7、个(360/5)的旋转和沿的旋转和沿51432510中垂线翻转构成。中垂线翻转构成。5123454321;34512543211234554321;4512354321;2345154321;4321554321;3215454321;2154354321;1543254321;5432154321543214535251505；和11对每个置换用下表描述循环因式分解对每个置换用下表描述循环因式分解置置 换换循环的因式分解循环的因式分解1 。2 。3 。4 。51 2 3 4 51 3 5 2 41 4 2 5 31 5 4 3 21 。2 5 。3 41 3 。2 。4 51 5 。3 。2

8、 41 2 。3 5 。41 4 。2 3 。505152535451234512注意：沿中垂线翻转时，有一个顶点位置没有改注意：沿中垂线翻转时，有一个顶点位置没有改 变，所以变，所以5个翻转置换的循环因子中，总有个翻转置换的循环因子中，总有一个一个1-循环出现。循环出现。 下面我们再讨论循环因子在着色问题中应用：下面我们再讨论循环因子在着色问题中应用：例：设例：设 f 是集合是集合X = 1,2,3,n的一个置换的一个置换:283567194987654321f这个置换的循环因式分解为：这个置换的循环因式分解为：13 f =1 4 7 3 。2 9 。5 6 。8 假设我们能使用的颜色是红色

9、、白色和蓝色，假设我们能使用的颜色是红色、白色和蓝色，C是所有这样的着色构成的集合。问置换是所有这样的着色构成的集合。问置换 f 保保持持C中着色不变的中着色不变的 |C( f )| 是多少？是多少？解：设解：设c是保持置换是保持置换 f 下不变的着色下不变的着色: f * c = c ;先先考虑考虑4-循环循环1 4 7 3，该循环将，该循环将1的颜色变到的颜色变到4的颜色，的颜色，4的颜色变到的颜色变到7的颜色，的颜色，由于由于f 使使得得 c 不变，只能是它们有相同的着色不变，只能是它们有相同的着色 ;同理同理14 2-循环循环2 9和和5 6中两点各分别着同一颜色，中两点各分别着同一颜

10、色， 1-循环循环8没有限制，可以着三种颜色的任没有限制，可以着三种颜色的任意一种色，我们对四个循环因子的每一个都能意一种色，我们对四个循环因子的每一个都能提供三种颜色，如同对四个格子可重复填提供三种颜色，如同对四个格子可重复填3个个号码，共计有：号码，共计有：34 = 81种着色。种着色。 将本题扩展到多个循环因子和将本题扩展到多个循环因子和k种颜色的种颜色的一般情况中去，将置换一般情况中去，将置换 f 的循环因子分解中的循环因子分解中的循环因子数量记为：的循环因子数量记为： # (f ) ；15定理定理14.3.1设设 f 是集合是集合X 的一个置换的一个置换, 假如用假如用k种颜种颜 色

11、对色对X 的元素着色，令的元素着色，令C是是X 的所有着色的的所有着色的集合，则集合，则 f 保持保持C中中着色不变着色不变的着色数为：的着色数为： |C( f )| = k#( f )例：用红色、白色和蓝色对正方形角点进行着例：用红色、白色和蓝色对正方形角点进行着色，问有多少色，问有多少不等价不等价的着色方案数？的着色方案数？解：正方形角点的置换共解：正方形角点的置换共8种，与循环因子关系种，与循环因子关系如下：如下：16置置 换换 f循环因子分解循环因子分解#( f )|C( f )|1 。2 。3 。4 434=811 2 3 4 131=31 3 。2 4 232=91 4 3 2 1

12、31=31 。2 4 。3 333=271 3 。2 。4 333=271 2 。3 4 232=91 4 。2 3 232=9041424341234由由Burnside定理得定理得C中不等价的着色数量中不等价的着色数量N(G,C)：21899272739381)(1),(GffCGCGN17 利用利用Burnside定理和定理定理和定理14.3.1给出的公式给出的公式)(#)()(1),(fGfkfCfCGCGN和 为我们提供了计算集合为我们提供了计算集合(在集合在集合X的一个置换群的一个置换群G的作用下的作用下)C中中不等价着色数不等价着色数的方法，其中的方法，其中, C是用给定颜色集对

13、是用给定颜色集对X的所有着色的集合。该方的所有着色的集合。该方法需要对各个置换求出循环因子分解；我们还法需要对各个置换求出循环因子分解；我们还可以引入置换个数的生成函数来解决此类问题。可以引入置换个数的生成函数来解决此类问题。18置换数的生成函数置换数的生成函数 令令 f 是含有是含有n个元素的集合个元素的集合X的一个置换。的一个置换。假设假设 f 的循环因子分解中有个的循环因子分解中有个e1个个1-循环循环, e2个个2-循环循环, en个个n-循环。因为循环。因为X的每一个元素的每一个元素仅仅出现在置换仅仅出现在置换 f 的某个循环因子中，所以，的某个循环因子中，所以，非负整数非负整数e1

14、, e2 , e3 ,. en满足满足: 1e1+2e2+3e3+. +nen = n我们将我们将n元组元组(e1, e2 , e3 ,. en)称为置换称为置换 f 的的型型。19记为：记为：type( f ) = (e1, e2 , e3 ,. en), 注意，我们注意，我们 定义过置换定义过置换 f 的循环因子数量记为：的循环因子数量记为：# f 那么：那么：# (f ) = e1+e2+e3+. +en 对每个对每个f 都有自都有自己的型；因为己的型；因为 f 的型仅仅取决于的型仅仅取决于k-循环中的循环中的阶数阶数k，不关心每个元素在哪个循环中，所以，不关心每个元素在哪个循环中，所以

15、，不同的置换可以得到不同的置换可以得到相同相同的型。但置换的型的型。但置换的型仅仅能描述置换的循环因子分解中各个长度仅仅能描述置换的循环因子分解中各个长度因子的因子的个数个数，不能清楚每个循环的具体结构。，不能清楚每个循环的具体结构。20例如：对于集合例如：对于集合X=1,2,3,n，定义，定义X上的一个上的一个 置换：置换： f =1 4 7 3 。2 9 。5 6 。8f 的型为的型为(1,2,0,1) 还有：还有：e1=1; e2 =2; e3 =0; e4= 1；并有关系：并有关系：1e1+2e2+3e3+4e4 = 1+22+30+41= 9 成立成立 这个数正好是集合这个数正好是集

16、合X的基数。的基数。 我们引入我们引入n个未知量：个未知量：z1, z2, z3, ., zn。其中，。其中，每个每个zk对应一个对应一个k-循环循环(k =1,2,3,.n)。21对于具有型为：对于具有型为： type( f ) = (e1, e2 , e3 ,. en) 的的 每个置换每个置换 f ，定义置换，定义置换 f 的单项式为：的单项式为：neneeezzzzfmon.)(321321 注意：置换注意：置换 f 单项式的次数单项式的次数(幂幂)为为f 的循环因的循环因子中循环个数的和子中循环个数的和: # (f ) = e1+e2+. +en 。 各置换的型决定了各置换的单项式，根

17、据定各置换的型决定了各置换的单项式，根据定理理14.3.1还能求出各置换作用还能求出各置换作用k个颜色集合个颜色集合C中着中着色不变的着色数：色不变的着色数： |C( f )| = k#( f )22 下面引入置换按照它的下面引入置换按照它的型型得到的生成函数：得到的生成函数： 设设G为为X上的一个置换群，对上的一个置换群，对G中的每一个置中的每一个置 换换 f 的单项式求和，称该和式为的单项式求和，称该和式为G中的置换中的置换f 按照型的生成函数按照型的生成函数。GfeneeeGfnzzzzfmon.)(321321 如果合并和式中的同类项，单项式如果合并和式中的同类项，单项式 的系数等于型

18、为的系数等于型为(e1, e2 , . en)的的G中的置换个数，中的置换个数，取定取定zk的颜色数量就得到不变的着色数的颜色数量就得到不变的着色数|C( f )| 。neneezzz.212123 定义：置换群定义：置换群G中的置换中的置换 f 按照型的生成函数按照型的生成函数 除以除以G中的置换个数中的置换个数|G|，称为，称为置换群置换群G的的循循环指数环指数。记为：。记为：PG (z1, z2 , z3 ,. zn) ;GfeneeenGnzzzzGzzzzP.1),.,(321321321 循环指数描述了循环指数描述了G中每个置换的循环因子结构。中每个置换的循环因子结构。例：求正方形

19、顶点关于平面旋转、翻转构成的例：求正方形顶点关于平面旋转、翻转构成的8阶二面体群阶二面体群D4的循环指数。的循环指数。解：列表描述置换、循环因子、型和置换单项式解：列表描述置换、循环因子、型和置换单项式24 8阶二面体群阶二面体群循环指数循环指数:f循环因子分解循环因子分解型型单项式单项式1 。2 。3 。4 (4, 0, 0, 0)1 2 3 4 (0, 0, 0, 1)1 3 。2 4 (0, 2, 0, 0)1 4 3 2 (0, 0, 0, 1)1 。2 4 。3 (2, 1, 0, 0)1 3 。2 。4 (2, 1, 0, 0)1 2 。3 4 (0, 2, 0, 0)1 4 。2

20、 3 (0, 2, 0, 0)0434241421434104030241zzzzz1414030201zzzzz2204032201zzzzz122104031221zzzzzz1414030201zzzzz122104031221zzzzzz2204032201zzzzz2204032201zzzzz)232(81),(122122144143214zzzzzzzzzPD25如果我们知道集合如果我们知道集合X的置换群的置换群G的循环指数的循环指数, 那么那么 就能用指定的颜色集合，在就能用指定的颜色集合，在X的所有着色的所有着色集中求出集中求出不等价不等价的着色数量；的着色数量；定理定理1

21、4.3.2 设设X是是n个元素的集合，假设用个元素的集合，假设用k种现种现有的颜色对有的颜色对X的元素着色。令的元素着色。令C是是X的所有的所有kn种种着色的集合，着色的集合，G是是X的一个置换群。则不等价的一个置换群。则不等价的着色数是用的着色数是用 zi=k (i=1,2,.n)代入代入G的循环的循环数中而得到的数，即：数中而得到的数，即：26 |N( G, C )| = PG(k, k,. ,k) 证明：由证明：由P358 Burnside定理定理(定理定理14.2.3)和和P365 定理定理14.3.1； G的循环指数是的循环指数是G中置换中置换 f 的单项式求和的平均值，即：的单项式

22、求和的平均值，即：GfeneeenGnzzzzGzzzP.1),.,(32132121 由定理由定理14.3.1可知，置换可知，置换 f 保持保持C 中着色不变中着色不变的着色数是：的着色数是：nneeeeeefkkkkk.2121.#27其中其中(e1, e2 , e3 ,. en)是置换是置换 f 的型。再由定理的型。再由定理 14.2.3可得不等价的着色数是：可得不等价的着色数是：),.,(.1),(21kkkPkkkGCGNGGfeeen例：例：求对正方形顶点进行求对正方形顶点进行k种着色后，种着色后，正方形顶正方形顶点的点的8阶二面体群阶二面体群D4的不等价着色数是多少？的不等价着色

23、数是多少？解：我们已经有：解：我们已经有：)232(81),(122122144143214zzzzzzzzzPD28由定理由定理14.3.2，不等价着色数是：不等价着色数是：)232(81)232(81),(2342244kkkkkkkkkkkkkPD如果颜色数量是如果颜色数量是3种，则种，则不等价着色数是：不等价着色数是：21)6275481(81)3233323(81)3 , 3 , 3 , 3(2344DP29例例:令令X=1,2,.,6表示立方体的表示立方体的6个面个面, 1表顶面；表顶面； 3表底面；表底面； 2表迎面；表迎面；4表背面；表背面； 5和和6表左、表左、 右侧面。右侧

24、面。 C=b,w表示黑、白两种颜色。下面表示黑、白两种颜色。下面在旋转等价的意义下计算立方体染色的格式数。在旋转等价的意义下计算立方体染色的格式数。 解：首先构造立方体的解：首先构造立方体的旋转群旋转群G，并把一种着色，并把一种着色看作看作X到到A的一个映射，的一个映射，14235630上、下底面不动，每次旋转上、下底面不动，每次旋转(右转右转)一个面、一个面、 二个面、三个面，二个面、三个面， 可得可得X的的4个置换：个置换： f1: 132 6 4 5; f2: 132 46 5; f3: 132 5 4 6前、后面不动，每次旋转前、后面不动，每次旋转(逆时针逆时针)一个面、一个面、 二个

25、二个面、面、 三个面，三个面， 可得可得X的的3个置换：个置换： f4: 241 5 3 6; f5: 241 35 6; f6: 241 6 3 531 左、左、 右侧面不动，右侧面不动， 仿上可得三个置换：仿上可得三个置换： f7: 1 2 3 45 6; f: 1 32 456; f: 1 4 3 256 分别绕四条对角线旋转分别绕四条对角线旋转120、240可得可得8个置换个置换f10：1 4 56 3 2； f11：1 5 26 4 3 f12：1 5 46 2 3； f13：1 2 56 3 4 f14：1 2 63 4 5； f15：1 6 23 5 4 f16：1 6 43 5

26、 2； f17：1 4 63 2 532此外分别以六对对角平行棱线的中点为轴线旋转此外分别以六对对角平行棱线的中点为轴线旋转 180,共可产生共可产生6个不同置换：个不同置换： f18：1 56 32 4； f19：1 63 52 4 f20：1 24 35 6； f21：1 42 35 6 f22：2 56 41 3； f23：2 65 41 3再加单位元再加单位元(幺置换幺置换): f24：123456; 共有共有24个置换，它们的型、单项式如下表：个置换，它们的型、单项式如下表：33f循环因子分解循环因子分解型型单项式单项式 f1132 6 4 5(2, 0, 0, 1, 0, 0) f

27、2132 46 5(2, 2, 0, 0, 0, 0) f3132 5 4 6(2, 0, 0, 1, 0, 0) f4241 5 3 6(2, 0, 0, 1, 0, 0) f5241 35 6(2, 2, 0, 0, 0, 0) f6241 6 3 5(2, 0, 0, 1, 0, 0) f71 2 3 45 6(2, 0, 0, 1, 0, 0) f81 32 456(2, 2, 0, 0, 0, 0) f91 4 3 256(2, 0, 0, 1, 0, 0) f101 4 56 3 2(0, 0, 2, 0, 0, 0) f111 5 26 4 3(0, 0, 2, 0, 0, 0)

28、 f121 5 46 2 3(0, 0, 2, 0, 0, 0)1421040314030221zzzzzzzz1421040314030221zzzzzzzz23040304230201zzzzzzz1421040314030221zzzzzzzz1421040314030221zzzzzzzz1421040314030221zzzzzzzz2221040304032221zzzzzzzz2221040304032221zzzzzzzz1421040314030221zzzzzzzz2221040304032221zzzzzzzz23040304230201zzzzzzz2304030423

29、0201zzzzzzz34f循环因子分解循环因子分解型型单项式单项式 f131 2 56 3 4(0, 0, 2, 0, 0, 0) f141 2 63 4 5(0, 0, 2, 0, 0, 0) f151 6 23 5 4(0, 0, 2, 0, 0, 0) f161 6 43 5 2(0, 0, 2, 0, 0, 0) f171 4 63 2 5(0, 0, 2, 0, 0, 0) f181 56 32 4(0, 3, 0, 0, 0, 0) f191 63 5 2 4(0, 3, 0, 0, 0, 0) f201 24 35 6(0, 3, 0, 0, 0, 0) f211 42 35

30、6(0, 3, 0, 0, 0, 0) f222 56 4 1 3(0, 3, 0, 0, 0, 0) f232 65 4 1 3(0, 3, 0, 0, 0, 0) f24123456(6, 0, 0, 0, 0, 0)32040304033201zzzzzzz23040304230201zzzzzzz61040304030261zzzzzzz23040304230201zzzzzzz23040304230201zzzzzzz23040304230201zzzzzzz23040304230201zzzzzzz32040304033201zzzzzzz32040304033201zzzzzzz

31、32040304033201zzzzzzz32040304033201zzzzzzz32040304033201zzzzzzz35上述立方体的染色问题中，上述立方体的染色问题中， G的循环指数为的循环指数为:从而，六面体每面可染两种颜色的方案数为：从而，六面体每面可染两种颜色的方案数为： 248663),(2332421222161654321xxxxxxxxxxxxxPG102424024488686163642428262262232)2 , 2 , 2 , 2 , 2 , 2(282226GP36例例:正三角形正三角形V1V2V3，若以红、白、蓝三色涂染，若以红、白、蓝三色涂染 各顶点，

32、各顶点， 试求置换等价意义下的染色方案？试求置换等价意义下的染色方案？解解:构造三角形的旋转置换群构造三角形的旋转置换群G。分别绕形心旋。分别绕形心旋转转(逆旋逆旋) 0、 120、240可得三置换：可得三置换： f0: V1V2V3 ; f1: V1V2V3; f2: V3V2V1 分别绕三边中垂线翻转分别绕三边中垂线翻转180可得三个置换：可得三个置换：f3: V1V2V3; f4: V1V3V2; f5: V1V2V337故不同方案数为故不同方案数为106276276333323) 3 , 3 , 3(13GP例：对正四面体的例：对正四面体的4个顶点用个顶点用4种颜色着色，求置种颜色着色

33、，求置 换等价意义下的不同方案数。换等价意义下的不同方案数。 解：使正四面体解：使正四面体V1 V2 V3 V4重合的刚体运动有两重合的刚体运动有两类，一类是绕各面的中垂线分别旋转类，一类是绕各面的中垂线分别旋转 0、632),(12111331321xxxxxxxPG38120和和240；一类是绕过二对边中点的连线；一类是绕过二对边中点的连线 旋转旋转180，从而可得群，从而可得群G的各置换如下：的各置换如下：V1V2V3V4； V1V2V3V4 V1V4V3V2； V2V1 V3 V4 V2V4V3V1; V3V1 V2 V4 V3V4V2 V1; V4V1 V2 V3 V4V3 V2V1

34、; V1 V2V3 V4 V1 V3V2 V4; V1 V4V2 V3132439 置换的型分别为置换的型分别为: (4, 0, 0, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (1, 0, 1, 0); (0, 2, 0, 0); (0, 2, 0, 0); (0, 2, 0, 0); 对应的单项式和：对应的单项式和：x14+(x1x3+ x1x3+ x1x3+ x1x3+ x1x3+ x1x3+ x1x3+ x1x3)+(x22+x22 +x22)= x14+8x1x3 +3x