发布时间 : 星期一 文章组合数学中常见的计数方法更新完毕开始阅读2eae7a57f01dc281e53af07b
沈阳理工大学学士学位论文
被置换g不变的元的个数,则构形群G的轨道个数为
?O(x)?而关于轨的权和为
1Gg?G?λ(g)
1?W?Oi??_1Gg?Gfg?f??W?f?
引理4.2.4 构形f在置换g下不变,当且仅当f在g的每个循环的所有元上取值相同。 4.2.3 Pólya计数定理
构形计数级数H(x1,x2,?,xk)可以由图形计数级数h(x1,x2,?,xk)代入到构形群G的 循环指标中去而得到,即
22nn H(x1,x2,?,xk)?PG[h(x1,x2,?,xk],h(x12,x2,?,xk),…,h(x1n,x2,?,xk)] (4.1)
b1b2bn1Pólya计数定理:?W(F)?GFn?????2?W(r)[W(r)]?[W(r)]?????? ????g?G?r?R??r?R??r?R? ?PG[?W(r),?[W(r)]2,?,?[W(r)]n] (4.2)
r?Rr?Rr?R4.2.4 Pólya计数的例子与性质
例1 设D为全等三角形ABC的顶点集,R为红、白两种颜色之集。G为三次交错群A3={(A),(ABC),(ACB)} 。
若每个顶点都涂上R的一种颜色,试求对A3不变的着色格式的个数。
首先指定红、白两种颜色的权为x、y,那么图形计数级数为h(x1,x2)?x?y。易知构
1形群A3的循环指标是PA3(x1,x2,x3)?(x13?2x3),再把图形计数级数代入上述群指标,得
3到构形计数级数:
H(x1,x2,x3)?PA3(?W(r)),?[W(r)]3)
r?Rr?R1 =((x?y)3?2(x3?y3))
3
1 =(x3?3x2y?3xy2?y3?2x3?2y3)
3 =x3?x2y?xy2?y3 故着色格式有4种:x3,x2y,xy2,y3 。
其次,若指定两种颜色的权均为1,则图形计数级数是2,于是构形计数级为
33
沈阳理工大学学士学位论文
1H(x1,x2,x3)?PA3(2,2)?(23?2?2)?4
3分析:指定权的第一种方法对构形计数级数的计算较频繁,但结果能证明每个格式的结构;第二种方法计算较简单,但未能表明格式结构。因此,应视具体要求来选择适当的方法。
容易得到如下推论:
1)设D?{1,2,?,n},R?{a1,a2,?,am},G为构形群,则构形计数级数之数值为
H(x1,x2,?,xn)?PG(m,m,?,m)
2)试求用图形ai恰好ki次(i=1,2,…,m)的构形格式F的个数则是(4.2)式展开式中
km的系数。 W1k1W2k2?Wm例2 设D?{1,2,3},R?{0,1},G?{(1),(23)},那么构形集RD就是所有的三位二进制
数:001,010,011,100,101,110,111,“1”000。易知
1PG?(x13?x1x2)。我们指定0,1的权为x,y,则h(x1,x2)?x?y,代入
21H(x1,x2,x3)?PG[(x?y),(x2?y2)]?[(x?y)3?(x?y)(x2?y2)]
2 ?x3?2x2y?2xy2?y3
由此可见,这里6种格式,不同的格式有相同的权如x2y或xy2。现在的问题是如何具体地写出这些不同的格式呢?
首先,注意到构形群G是由置换(23)生成的循环群,我们利用g?(1)(23)作RD的一个置换g?(1)(2,4)(3,5)(6)(7)(8)其中g满足g(f)?fg。由此得到对G的构形格式与相应的G的生成置换g每一个循环相重合。于是有:001,010,011,110,111,000。容易看出在对换(2,4)和(3,5)里两个三位二进制数对G来说是等价的。因此只要选取一个作代表即可。
同样,对例1中的G是由置换(123)生成的,那么作RD上的相应置换得(124)(365)(7)(8) 。据此4个循环便有如下4种构形格式:001,011,111,000。因此,获得一个性质:
若构形群G是一个由置换g生成的循环群,则对G的构形格式,可由g在G里的相应置换g:g(f)?fg的每个循环里选取一个构形来作一种格式。
例3 设D为一个正四面体的顶点集合,R为红、白两种颜色的集合,G为正四面体的旋转群,试求每个顶点都涂上R的一种颜色的格式的个数。
解 设D={1,2,3,4},R={0,1},而G的元是:(1),(123)(4),(132)(4),
________34
沈阳理工大学学士学位论文
(124)(3),(142)(3),(134)(2),(143)(2),(234)(1),(243)(1),(12)(34),(13)(24),(14)(23).
RD:0001,0010,0011,0100,0101,0110,0111,1000,1001,1010,1011,1100,1101,11
10,1111,“1”0000。
利用G的元g作R置换g:g(f)?fg,得:
(1)(2)(3)(4)(5)(6)(7)(8)(9)(10)(11)(12)(13)(14)(15)(16); (1,2,4)(3,6,5)(7)(8)(9,10,12)(11,14,13)(15)(16); (1,4,2)(3,5,6)(7)(8)(9,12,10)(11,13,14)(15)(16); (1,4,8)(2)(3,6,10)(5,12,9)(7,14,11)(13)(15)(16); (184)(2)(3,10,6)(5,9,12)(7,11,14)(13)(15)(16); (1)(2,4,8)(3,5,9)(6,12,10)(7,13,11)(14)(15)(16); (1)(2,8,4)(3,9,5)(6,10,12)(7,11,13)(14)(15)(16); (1,2)(3)(4,8)(5,10)(6,9)(7,11)(12)(13,14)(15)(16); (1,4)(2,8)(3,12)(5)(6,9)(10)(11,14)(13,7)(15)(16); (1,8)(2,4)(3,12)(5,10)(6)(7,14)(9)(11,13)(15)(16); (1,2,8)(3,10,9)(4)(5,6,12)(7,14,13)(11)(15)(16); (1,8,2)(3,9,10)(4)(5,12,6)(7,13,14)(11)(15)(16);
由推论易求得5种构形格式:0001,1110,0011,1111,0000。 特别地,这里有三个颇有趣的性质:
1)四位二进制数构形集合对于逻辑加(不进位)运算做成一个群。
2)四位二进制数构形集对于由四次置换群G引入的一个同构的置换群G来说,g中每个k>1循环的全部二进制数的逻辑和恰等于它的某一个1一循环的二进制数。
3)在g里的全部1-循环的二进制数集对逻辑加运算来说作成一个群。
6,5)(7)(8)(9,10,12)(11,14,13)(15)(16) 例如g(123)(4)?(1,2,4)(3,__D____中有:1?2?4=7,3?6?5=0,9?10?12=15,11?14?13=8.注意把这些数转化为二进制数.
0 0 0 1 0 0 1 1 1 0 0 1 1 0 1 1 0 0 1 0 0 1 1 0 1 0 1 0 1 1 1 0
?0 1 0 0 ?0 1 0 1 ?1 1 0 0 ?1 1 0 1
0 1 1 1 0 0 0 0 1 1 1 1 1 0 0 0
35
沈阳理工大学学士学位论文
<{0111,1000,1111,0000},?>显然是一个群。因为0000是单位元,其余三个元都是以自身为逆元。
易知,对n位二进制数的构形集也具有此类性质,这也与循环字编码等有关。
36