《组合数学(26)解析》由会员分享，可在线阅读，更多相关《组合数学(26)解析（40页珍藏版）》请在金锄头文库上搜索。
1、第八章 Polya计数法 14.2 Burnside定理 前面我们已经讨论置换群的一些例子，本次 课我们要利用置换群的知识解决一些涂色问题, 这就是著名的Burnside(伯恩赛德)定理。 令X =1,2,3,n, G是集合X的一个置换群， X的一种着色是指对X的每一个元素指定一种颜 色。设C是X的一个着色方案的集合。即将X中 1 每一个元素着上色后够成的新集合。通常我们 有许多颜色可以着色,例如用红色或者蓝色 等。现在要求G以它置换的方式将C中的一种 着色对应到C中的另一种着色。 设c是X的一种着色 (方案)，其中的元素 1,2,3,n着色后的颜色分别是: c(1), c(2), c(3),
2、 c(n);令置换： 2 定义 f *c 是使得ik具有颜色c(k)的着色,即： (f *c)(ik) = c(k) 或者说 k元素经过置换 运算 f 得到ik ，再经过着色运算c后得到c(k) 。 着色集合C具有性质是： 对于置换群G中的任意置换元素 f 和着色群 C中的任意着色元素c， f *c 仍然属于C。或者 说 f 置换了C中的着色，那么G也成C中的置换 群，即：置换运算可以改变着色。 3 置换群G中的合成运算“ 。”，与置换群G中 的置换对C中着色运算“ * ”之间有下列基本 关系： ( g。f ) * c = g * (f * c) 左边是将元素k的颜色变到( g。f ) (k)
3、 ; 又边是将元素k的颜色先变到f (k) ，然后变化到 g(f (k)的着色 ; 例：上次课中我们讲过正四边形的角点关于平面 旋转和对称轴翻转可以构成对称群： 4 角点标以1、2、3、4，正方形存在两种类型的8 个置换。置换群表示如下： 现在对角点1、2、3、4 着以红色和蓝色。用R表 示红色，B表示蓝色，按照角点的顺序1,2,3,4 我们可以书写角点的 颜色，例如：红蓝蓝红 着色是： ( R,B,B,R ) 1 4 3 2 5 将 ( R,B,B,R )进行 置换， 就是平面旋转90得到： ( R,R,B,B ), 如右图中括号中 的角点。再进行 置换， 把平面再旋转90得到： ( B,R
4、,R,B ), 如右下图括号中 有下划线的角点。 角点标以1、2、3、4，正方形存在两种类型的8 个置换。置换群表示如下： 1(1) 43 2(4 ) (3)(2 ) 1(4) 43 2(3 ) (2)(1 ) 6 关于置换群 中的所有置换，我们列出下表： 置换换作用在原着色(R, B, B, R )上的效果 (R, B, B, R) (R, R, B, B) (B, R, R, B) (B, B, R, R) (R, R, B, B) (B, B, R, R) (B, R, R, B) (R, B, B, R) 7 通过 上表可以看出，置换 并不改变原 来的着色；每一种着色各出现两次(同色)
5、 。 定义：如果置换群Gc中存在一种置换，使得将 一种着色变成另一种着色，则称这两种着色是 等价的。f G;时 f *c1=c2 c1c2 f *c1c1 这里的等价与离散数学中“关系等价” 一样，具有：自反性，对称性和传递性，我们 同样可以用“c1c2”表示着色c1与c2等价。 8 例如： (R,B,B,R)(R,R,B,B)(B,R,R,B), 但是(R,B,B,R)(R,R,R,B)因为后者是三红 一蓝，所以着色等价的前提必须各种颜色出 现的数量要对应相同。 同样有(R,B,B,R)(R,B,R,B)，它们两种颜色的 相间不同，怎样旋转和翻转都不行； 特别地着色： (R,R,R,R)(R
6、,R,R,R) 自身等价； 与三红一蓝的着色等价的共有： 9 (R,R,R,B); (R,R, B,R); (R,B,R,R); (B,R,R,R)也可 以说它们构成了一个等价类, 对不同的着色 就够成不同的等价类。共有：C(4,2)类；我们给 出着色等价的一般性定义：令G是作用在集合X 的一个置换群，取X =1,2,3,n, 令C是X的一个 着色集合，使得对于G中的任意元 f 和C中的元c ， X的着色f *c 仍然属于C。于是，在这种意义 下G作用于C，对C中进行的着色仍然属于C 。 10 Burnside定理 设G是集合X =1,2,3,n 的一个置换群， C是G作用C上的对X的一个着色
7、集合。对于G 中的任意置换 f 和C中的任意着色 c f * c C 适当选择 f 和 c可使得： f * c = c 例如：对正四边形着色(R, B, B, R )后，平面旋转 11 0或者绕水平中位线翻转这两种置换都没有改 变原来的着色。我们把这种经过置换后而 着色c不变的置换组成集合，记为： G(c) = f | f G f * c = c 把这种经过置换 f 后而着色c保持不变的着色 组成集合，记为： C(f) = c | c C f * c = c 他们的区分是G(c) 中的元素是置换，而C(f) 中是 着色。并且称G(c) 是c的稳定核(c保持不变)。 12 定理14.2.1 对于
8、一种着色c，c的稳定核G(c) 是 一个置换群，并且对于G中的任意置换f和g ： g *c = f *c 当且仅当 f -1 。g G(c) 证明：该定理要证明两部分内容，一是证明稳 定核G(c)是一个置换群；二是证明g *c = f *c 的充要条件是 f -1 。g G(c)； 1）如果f 和g 都使得 c 保持不变 , 则先f 后g使 得 c 保持不变, 即(g 。f)(c) = c 。说明合成 13 运算“ 。”关于G(c) 封闭；显然单位元使得所 有着色不变；如果f 使得 c 不变， f -1 也使得 c 不变；满足构成群的三个条件， G(c) 是一个 置换群。 2）充分性：假设g
9、*c = f *c 由合成运算“ 。”，与着色运算“ * ”之间的基本关 系： ( g。f ) * c = g * (f * c) 有： 14 ( f -1 。g) * c = f -1 * ( g * c ) = f -1 * ( f * c ) = (f -1 * f )* c = * c = c ; 说明( f -1 。g) 也使 得c不变，故： ( f -1 。g) G(c) ； 必要性：假设( f -1 。g) G(c) ，那么有： ( f -1 。g) * c = c ，两边同时作f 置换：右边= f * c 左边= f *( f -1 。g) * c = f * f -1 * (
10、 g * c ) = * ( g * c ) = g * c; 证毕 15 该定理的应用，主要体现在下面这个推论上， 我们可以通过已知的一种着色c，去确定在 置换群G的作用下不同的着色数量。 推论14.2.2： 设c为C中的一种着色，那么： 即：与c的等价的着色(f*c)数量等于G中的置换 数量与c的稳定核G(c)中的置换数量之商； 16 证明：设G是作用在着色集合C上的置换群，对 于C中的每一种着色方案c，通个置换群G中 的|G |个置换 fi (i =1,2,|G|)作用于着色c后， 得到与c等价的着色 fi *c 共|G |个，即一个置换 就得到一个等价的着色。而G中一些置换使得 部分着
11、色不变，即这部分置换在同一稳定核里 ；例如前面题：正四边形的角点关于平面旋转 和对称轴翻转可以构成对称群，对(R, B, B, R) 17 着色， 置换群中的部分置换能够组成稳定核： (R, B, B, R) (R, R, B, B) (B, R, R, B) (B, B, R, R) |G| = 8， |G(c)| = 2， |f *c | f G | = 4；所以 |G| = |G(c)|f *c | f G | ； 稳定核都是由两个 置换组成，而等价 的着色正好是4类， 故有关系： 18 例：正四边形的角点三红一蓝的着色c等价的共有 ： (R,R,R,B); (R,R, B,R); (R
12、,B,R,R); (B,R,R,R) 那么： 而置换群中元素的数量 ： 且稳定核G(c)中的置换仅仅有： 平面旋转0和绕对角线翻转两个。 它们的关系是： 1 4 3 2 19 前面讨论是等价的着色,下面的Burnside定理给 出了计算不等价着色数量的公式。 定理14.2.3 设G是X的一个置换群，C是X的一个 着色集并且使得对于G中的任意f与C中的任意c ，f *c属于C，则C中不等价的着色数量N(G,C) 为: 即： C中不等价的着色数量等于通过G中的置换 保持不变的着色数量的平均数。 20 证明：我们可以分别采取以置换f和着色c两种不 同路线方式计数，然后证明两个计数相等。 对于 f 使
13、得c保持不变，即：f *c = c 的数量用 序偶 (f , c)的数量决定： 它可以分别由 f 和c两方面来求。 第一种计数方式是： 考察G中的每个置换 f ，并计算 f 保持着色 21 不变的着色数量，然后相加所有的数量得到和。 因为C( f ) 是通过 f 保持不变的着色集合， 用这种计数方式计数得到： 另一种计数方式： 是考察C中的每个c，计算满足：f *c = c的 置换 f 的个数，然后相加得到所有的数量的和 。对于每种着色 c，满足f *c = c 的所有置换 f 的 22 集合就是我们定义过的稳定核G(c) ，因此， 每种着色 c 对和的贡献是该着色稳定核中 的置换数：|G(c
14、) |，由推论： 于是，通过这种方式得到的所有着色的和是： 即：所有着色的稳定核中的置换数之和。 23 但如果我们按等价类将着色归类，那么上式 可以简化。在同一等价类中，有|G|个置换 对着色c作用，使得每个等价类对和的总贡献是 ：|G|。由于等价类的个数就是不等价的着色数 量N(G,C)，所以： 24 例： 将一正方形等分成4格，用白、绿2种颜色 着色，若经旋转可以吻合的方案算作同一 个方案， 问能得到多少种不同方案的图像。 解：设每格有白、绿两种颜色可供选择，故所有 可能的图像共有24种， 记为X=X1, X2, , X16 。 当每个图像都绕中心轴逆时针旋转0, 0,180,270时，都
15、可得到X的一种排列，记4 种旋转置换的排列为G=f0, f90, f180, f270。 25 | G | = 4。从而问题归结为求置换群G的平面旋 不等价类数量。 用a表示着白色,用b表示着绿色， (4a, 0b) 为4白0绿的着色，具体为(a,a,a,a)。 (3a, 1b) 为3白1绿的着色,具体为(b,a,a,a) (a,b,a,a) (a,a,b,a,) (a,a,a,b)四个构成一等价类。还有 (2a, 2b), (1a, 3b), (0a, 4b)等形式 。 26 1 2 3 4 5 6 7 8 9 10 11 12 13 14 15 16 不难求得C( f0 )=16, 每种着色后旋转0 都不变， C( f90 )=2，有两种着色(1和2)旋转90 不变， C( f180 )=4,有四种着色(1,2,11,12)旋转180 不变 ， C( f270 )=2，有两种着色(1和2)旋转270 不变, 27 故G的不同等价类数为: 亦即在旋转吻合的前提下共有6种（不同等 价类）图案。 例:(循环排列计数)把n个不同的对象放在一个圆上 ，问有多少种放法？ 28 解：问题相当于用n种不同的颜色对正n边形 的角点着色，再进行360/n种旋转置换，求 旋转群的不等价的着色数。 令C是由对正n边形角点进行每种着色的颜色 只出现一次的所有n!种着色方案的集合。作用 在C上
