组合数学之母函数形式Polya定理及其应用

《组合数学》第十一讲

母函数形式Polya定理及其应用

第十一讲: 内容提要I. Polya定理及其证明* II. 母函数形式的Polya定理

III. Boole函数的计数 IV. 图简单图的计数*

I. Pò lya定理及其证明*Pò lya定理 设G是n元集合S上的置换群, CS是用集合C中m种颜色对S中元素进 行染色的全部方案组成的集合, 则CS 中在G作用下互不等价的染色方案数 为:PG ( m , m , , m ) | G | 1

g G

m

c(g)

其中PG(x1,x2,…,xn)为置换群G的轮换指标, c(g)是置换g中不相交轮换总数. 若g 的类型为(c1,c2,…,cn), 则 c(g)=c1+c2+…+cn. 我们给出的其实是特殊形式的Polya 定理, 更一般形式的是带权的形式. 可 以用来计算有条件限制的计数问题. 下面我们简单介绍Polya定理的证明.4

15 9 13

26 10 14

3 711 15

4 8 12 165

证明 设CS是n个对象集合S={a1,a2,…,an} 用m种颜色C={c1,c2,…,cm}进行涂色 所得的全部方案的集合. 显然 |CS|=mn. 对于置换群G中任何一个元素g, 它 是S的一个置换, 自然也诱导出CS上 的一个置换g*. 具体方式: g*: f fg, f CS. 即：g*(f)=fg, 或：(g*(f))(a)=f(g(a)), a S.6

G*={g*|g G}构成CS的一个置换群, 而且|G*|=|G|. 互不等价的染色方案数正好是G*在 CS上的不同轨道数目. 而要计算轨道数目, 需要应用 Burnside引理. 既然|G*|=|G|, 我们只 需要计算G*中每个元素不动点数目. 设g G, 下面来计算g*的不动点的数 目.不仿设置换g的轮换分解如下:g=(a,b,c, …, p, q)(r,s,…, t)…(u,v,…,w),7

如果f CS在g*下不动, 即g*(f)=f, 那么 f(b)=f(g(a))=f(a), 类似可以得到 f(c) =…=f(p)=f(q)=f(a). 说明轮换(a, b, c, …, p, q)中的元素颜 色相同. 同样有, f(r)=f(s)=…=f(t); …; f(u)=f(v)=…=f(w). 由此可见, 如果f是g*的一个不动点, 那么f一定把位于置换g的同一个轮换 中的元素染成了同样的颜色.8

反过来, 如果f把位于g的同一个轮换 中的元素染成同样的颜色, 则必然是 g*的不动点. 这样g*不动点的数目就等于这样染色 的数目, 它把g的同一个轮换中的元素 染同样的颜色. 因为g有c(g)个轮换, 每个轮换可以染 一种颜色, 共有mc(g) 种不同的染色方 案. 所以, c1(g*)=mc(g). 由Burnside引理可以得到结论. 9

II. 母函数形式的Pò lya定理 我们这里给出的Polya计数定理其实是一 种特殊形式. 一般形式的Polya定理还可以 用来解决有条件限制而且互相不等价的染 色方案数目. 还有一个问题是如何列举出所有不同类型 的染色方案? 显然Polya定理无法告诉我 们这些. 它只能告诉我们总数. 母函数形式Polya定理可以满足这个要求.10

先通过一个简单例题说明思想.例1. 假设要用b, g, r, y这4种颜色涂染3个同样 的球, 则所有方案可形

式地表示为 (b+g+r+y)3. 由于三个球无区别, 故乘法是 可交换的, 例如b2g=gb2. 把这个形式展开: (b+g+r+y)3=b3+g3+r3+y3+3b2g+3b2r+3b2y +3g2b+3g2r+3g2y+3r2b+3r2g+3r2y+3y2g +3y2r+3y2b+6bgr+6bgy+6brg+6gry 展开式中的不同项表示不同的方案, 每项 系数表示该方案的数目. 11

只要把上面这种思想方法用于Polya 定理, 就可以得到母函数形式Polya定 理. 设G是n个对象集合S={a1,a2,…,an}上 的一个置换群, 要用m种颜色b1,b2, , bm进行染色, 我们需要讨论并决定互 不等价的染色方案的情况. 根据Polya 定理, 不等价的染色方案数目可以通 过下面的公式得到:PG ( m , m , , m ) | G | 1

g G

m

c(g)12

其中c(g)是置换g的轮换总数目, 而PG ( x 1 , x 2 , , x n ) | G | 1

g G

x1 x 2 x n

c1

c2

cn

是置换群G的轮换指标. 如果置换g的类型为: (c1(g),c2(g),…,cn(g)), c(g)=c1(g)+c2(g)+…+cn(g), 我们知道mc(g)

m

c1 ( g )

m

c2 ( g )

m

cn ( g )13

其含义是让置换g的ci个长为i的轮换 中每个轮换中的元素染同样的颜色, 这是为了得到由g诱导出的置换g*的 不动点. 当时我们并不关注这个同样的颜色究 竟是哪一种颜色. 现在我们想列举出 染色方案情况, 就需要关注这个问题. 根据刚才例题的思想, 对应于置换g的 每个长为i的轮换因子, 其中i个元素 的颜色可以形式的表示为:b1 b 2 b mi i i14

既然g有ci=ci(g)个长为i的轮换, 自然 长为i的轮换中出现的元素的染色方 案可以形式的表示为:( b1 b 2 b m )i i i ci ( g )

考虑到g的全部轮换分解情况, 相应于 置换g的染色方案可以形式表示为:( b1 b 2 b m )c1 ( g )

( b1 b 2 b m )n n n

cn ( g )

由此可以知道, 总的染色方案的列举 只要在轮换指标中令:x i b1 b 2 b mi i i15

即可得到能列举出方案情况的母函数 形式的Polya定理:p | G | 1

g G

( b1 b m )

c1 ( g )

( b1 b m )n n

cn ( g )

这就是母函数形式的Polya定理的计 数公式, 在具体应用中展开并按照同 类项整理, 即可列举出不同的方案情 况和数目. 下面通过一个例题来说明.16

例2 有3种不同颜色的珠子, 用它们串成4 个珠子的项链. 问一共能串成多少种 不同类型的项链? 列举出全部不同类 型的方案.v4 v1

v3

v2

解 先要确定保持图形与原来位置重合的 置换群G.17

容易看出来使得项链运动前后重合的 置换群G含有以下8个置换:(v1)(v2)(v3)(v4), (v2)(v4)(v1v3), (v1)(v3)(v2v4), (v1v3) (v2v4), (v1v2) (v3v4), (v1v4) (v2v3), (v1v2v3v4), (v4v3v2v1),

共有4种类型的置换, 容易写出其轮换 指标公式:PG ( x 1 , x 2 , x 3 , x 4 ) 1 8 ( x 1 2 x 1 x 2

3 x 2 2 x 4 ),4 2 2

总方案数PG ( 3 , 3 , 3 ) 1 8 (34

2 3

3

3 3

2

2 3 ) 21 .

如果要列举出具体方案情况, 需要利 用母函数形式的Polya定理. 为书写方 便, 我们用b, r, g分别表示这三种颜色. 具体的方案需要展开下面的式子: P=8-1[(b+g+r)4 + 2(b+g+r)2(b2+g2+r2) + 3(b2+g2+r2)2 + 2(b4+g4+r4)]19