组合数学中常见的计数方法

沈阳理工大学学士学位论文

被置换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)

>>展开全文<<
12@gma联系客服:779662525#qq.com(#替换为@)