组合数学(26)

1、1第八章第八章 Polya计数法计数法14.2 Burnside定理定理 前面我们已经讨论置换群的一些例子，本次前面我们已经讨论置换群的一些例子，本次课我们要利用置换群的知识解决一些涂色问题课我们要利用置换群的知识解决一些涂色问题,这就是著名的这就是著名的Burnside(伯恩赛德伯恩赛德)定理。定理。 令令X =1,2,3,n, G是集合是集合X的一个置换群，的一个置换群， X的一种着色是指对的一种着色是指对X的每一个元素指定一种颜的每一个元素指定一种颜色。设色。设C是是X的一个着色方案的集合。即将的一个着色方案的集合。即将X中中2每一个元素着上色后够成的新集合。通常我们每一个元素着上色后够

2、成的新集合。通常我们 有许多颜色可以着色有许多颜色可以着色,例如用红色或者蓝色例如用红色或者蓝色等。现在要求等。现在要求G以它置换的方式将以它置换的方式将C中的一种中的一种着色对应到着色对应到C中的另一种着色。中的另一种着色。 设设c是是X的一种着色的一种着色 (方案方案)，其中的元素，其中的元素1,2,3,n着色后的颜色分别是着色后的颜色分别是: c(1), c(2), c(3), c(n);令置换：令置换：niiinf21213 定义定义 f *c 是使得是使得ik具有颜色具有颜色c(k)的着色的着色,即：即： (f *c)(ik) = c(k) 或者说或者说 k元素经过置换元素经过置换运

3、算运算 f 得到得到ik ，再经过着色运算，再经过着色运算c后得到后得到c(k) 。 着色集合着色集合C具有性质是：具有性质是： 对于置换群对于置换群G中的任意置换元素中的任意置换元素 f 和着色群和着色群C中的任意着色元素中的任意着色元素c， f *c 仍然属于仍然属于C。或者。或者说说 f 置换了置换了C中的着色，那么中的着色，那么G也成也成C中的置换中的置换群，即：置换运算可以改变着色。群，即：置换运算可以改变着色。4 置换群置换群G中的合成运算中的合成运算“ 。”，与置换群，与置换群G中中 的置换对的置换对C中着色运算中着色运算“ * ”之间有下列基之间有下列基本关系：本关系： ( g

4、。f ) * c = g * (f * c) 左边是将元素左边是将元素k的颜色变到的颜色变到( g。f ) (k) ; 又边是将元素又边是将元素k的颜色先变到的颜色先变到f (k) ，然后变化，然后变化到到 g(f (k)的着色的着色 ;例：上次课中我们讲过正四边形的角点关于平例：上次课中我们讲过正四边形的角点关于平面旋转和对称轴翻转可以构成对称群：面旋转和对称轴翻转可以构成对称群：5角点标以角点标以1、2、3、4，正方形存在两种类型的，正方形存在两种类型的8 个置换。置换群表示如下：个置换。置换群表示如下：现在对角点现在对角点1、2、3、4 着以红色和蓝色。用着以红色和蓝色。用R表表示红色，

5、示红色，B表示蓝色，按照角点的顺序表示蓝色，按照角点的顺序1,2,3,4我们可以书写角点的我们可以书写角点的 颜色，例如：红蓝蓝红颜色，例如：红蓝蓝红 着色是：着色是： ( R,B,B,R ),432134241404cG14326将将 ( R,B,B,R )进行进行 置换，置换， 就是平面旋转就是平面旋转90得到：得到： ( R,R,B,B ), 如右图中括号中如右图中括号中 的角点。再进行的角点。再进行 置换，置换， 把平面再旋转把平面再旋转90得到：得到： ( B,R,R,B ), 如右下图括号中如右下图括号中有下划线的角点。有下划线的角点。141(1)432(4)(3)(2)241(4

6、)432(3)(2)(1)7关于置换群关于置换群 中的所有置换，我们列出下表：中的所有置换，我们列出下表：,432134241404cG置换置换作用在原着色作用在原着色(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)0414342412348通过通过 上表可以看出，置换上表可以看出，置换 并不改变原并不改变原 来的着色；每一种着色各出现两次来的着色；每一种着色各出现两次(同色同色)。定义：如果置换群定义：如果置

7、换群Gc中存在一种置换，使得将中存在一种置换，使得将一种着色变成另一种着色，则称这两种着色是一种着色变成另一种着色，则称这两种着色是等价的等价的。f G;时时 f *c1=c2 c1c2 f *c1c1 这里的等价与这里的等价与离散数学离散数学中中“关系等价关系等价”一样，具有：自反性，对称性和传递性，我们一样，具有：自反性，对称性和传递性，我们同样可以用同样可以用“c1c2”表示着色表示着色c1与与c2等价。等价。404和9例如：例如： (R,B,B,R)(R,R,B,B)(B,R,R,B), 但是但是(R,B,B,R)(R,R,R,B)因为后者是三红因为后者是三红一蓝，所以着色等价的前提必

8、须各种颜色出一蓝，所以着色等价的前提必须各种颜色出现的数量要对应相同。现的数量要对应相同。同样有同样有(R,B,B,R)(R,B,R,B)，它们两种颜色的，它们两种颜色的相间不同，怎样旋转和翻转都不行；相间不同，怎样旋转和翻转都不行；特别地着色：特别地着色： (R,R,R,R)(R,R,R,R) 自身等价；自身等价； 与三红一蓝的着色等价的共有：与三红一蓝的着色等价的共有：10 (R,R,R,B); (R,R, B,R); (R,B,R,R); (B,R,R,R)也可也可 以说它们构成了一个等价类以说它们构成了一个等价类, 对不同的着色对不同的着色就够成不同的等价类。共有：就够成不同的等价类。

9、共有：C(4,2)类；我们给类；我们给出着色等价的一般性定义：令出着色等价的一般性定义：令G是作用在集合是作用在集合X的一个置换群，取的一个置换群，取X =1,2,3,n, 令令C是是X的一的一个着色集合，使得对于个着色集合，使得对于G中的任意元中的任意元 f 和和C中的中的元元c， X的着色的着色f *c 仍然属于仍然属于C。于是，在这种意。于是，在这种意义下义下G作用于作用于C，对，对C中进行的着色仍然属于中进行的着色仍然属于C 。11Burnside定理定理 设设G是集合是集合X =1,2,3,n 的一个置换群，的一个置换群， C是是G作用作用C上的对上的对X的一个着色集合。对于的一个着

10、色集合。对于G中的任意置换中的任意置换 f 和和C中的任意着色中的任意着色 c f * c C 适当选择适当选择 f 和和 c可使得：可使得： f * c = c例如：对正四边形着色例如：对正四边形着色(R, B, B, R )后，平面旋转后，平面旋转12 0或者绕水平中位线翻转这两种置换都没有或者绕水平中位线翻转这两种置换都没有改改 变原来的着色。我们把这种经过置换后而变原来的着色。我们把这种经过置换后而着色着色c不变的不变的置换组成集合置换组成集合，记为：，记为： G(c) = f | f G f * c = c 把这种经过置换把这种经过置换 f 后而着色后而着色c保持不变的保持不变的着色

11、着色组成集合组成集合，记为：，记为： C(f) = c | c C f * c = c 他们的区分是他们的区分是G(c) 中的元素是置换，而中的元素是置换，而C(f) 中是中是着色。并且称着色。并且称G(c) 是是c的的稳定核稳定核(c保持不变保持不变)。13定理定理14.2.1 对于一种着色对于一种着色c，c的稳定核的稳定核G(c) 是是 一个置换群，并且对于一个置换群，并且对于G中的任意置换中的任意置换f和和g： g *c = f *c 当且仅当当且仅当 f -1 。g G(c) 证明：该定理要证明两部分内容，一是证明稳证明：该定理要证明两部分内容，一是证明稳定核定核G(c)是一个置换群；

12、二是证明是一个置换群；二是证明g *c = f *c 的充要条件是的充要条件是 f -1 。g G(c)； 1）如果）如果f 和和g 都使得都使得 c 保持不变保持不变 , 则先则先f 后后g使使得得 c 保持不变保持不变, 即即(g 。f)(c) = c 。说明合成。说明合成14运算运算“ 。”关于关于G(c) 封闭；显然单位元封闭；显然单位元使得所使得所 有着色不变；如果有着色不变；如果f 使得使得 c 不变，不变， f -1 也也使得使得 c 不变；满足构成群的三个条件，不变；满足构成群的三个条件， G(c) 是一个是一个置换群。置换群。2）充分性：假设）充分性：假设g *c = f *

13、c由合成运算由合成运算“ 。”，与着色运算，与着色运算“ * ”之间的基之间的基本关系：本关系： ( g。f ) * c = g * (f * c) 有：有：15 ( 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 *

14、 c 左边左边= f *( f -1 。g) * c = f * f -1 * ( g * c ) = * ( g * c ) = g * c; 证毕证毕16该定理的应用，主要体现在下面这个推论上，该定理的应用，主要体现在下面这个推论上， 我们可以通过已知的一种着色我们可以通过已知的一种着色c，去确定在，去确定在置换群置换群G的作用下不同的着色数量。的作用下不同的着色数量。推论推论14.2.2： 设设c为为C中的一种着色，那么：中的一种着色，那么：)()(GfcfcGGcGGGfcf或即：与即：与c的的等价等价的的着色着色(f*c)数量数量等于等于G中的中的置换置换数量数量与与c的的稳定核稳定

15、核G(c)中的置换数量中的置换数量之商之商；17证明：设证明：设G是作用在着色集合是作用在着色集合C上的置换群，对上的置换群，对 于于C中的每一种着色方案中的每一种着色方案c，通个置换群，通个置换群G中中的的|G |个置换个置换 fi (i =1,2,|G|)作用于着色作用于着色c后，后，得到与得到与c等价的着色等价的着色 fi *c 共共|G |个，即一个置换个，即一个置换就得到一个等价的着色。而就得到一个等价的着色。而G中一些置换使得中一些置换使得部分着色不变，即这部分置换在同一稳定核里；部分着色不变，即这部分置换在同一稳定核里；例如前面题：正四边形的角点关于平面旋转和例如前面题：正四边形

16、的角点关于平面旋转和对称轴翻转可以构成对称群，对对称轴翻转可以构成对称群，对(R, B, B, R)18着色，着色， 置换群中的部分置换能够组成稳定核：置换群中的部分置换能够组成稳定核： (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 | ；,432134241404cG,404,114,334,224稳定核都是由两个稳定核都是由两个置换组成，而等价置换组成，而等价的着色正好是的着色正好是4类，类，故有关

17、系：故有关系：19例：正四边形的角点三红一蓝的着色例：正四边形的角点三红一蓝的着色c等价的共有：等价的共有： (R,R,R,B); (R,R, B,R); (R,B,R,R); (B,R,R,R)那么：那么： 而置换群中元素的数量：而置换群中元素的数量：且稳定核且稳定核G(c)中的置换仅仅有：中的置换仅仅有：平面旋转平面旋转0和绕对角线翻转两个。和绕对角线翻转两个。 它们的关系是：它们的关系是：4Gfcf8,432134241404G1432)(2)(GfcfcGGcG20 前面讨论是前面讨论是等价等价的着色的着色,下面的下面的Burnside定理给定理给 出了计算出了计算不等价不等价着色数量

18、的公式。着色数量的公式。 定理定理14.2.3 设设G是是X的一个置换群，的一个置换群，C是是X的一个的一个着色集并且使得对于着色集并且使得对于G中的任意中的任意f与与C中的任意中的任意c，f *c属于属于C，则，则C中不等价的着色数量中不等价的着色数量N(G,C)为为:GffCGCGN)(1),( 即：即： C C中不等价的着色数量等于通过中不等价的着色数量等于通过G G中的置换中的置换保持不变的着色数量的保持不变的着色数量的平均数平均数。21证明：我们可以分别采取以置换证明：我们可以分别采取以置换f和着色和着色c两种不两种不 同路线方式计数，然后证明两个计数相等。同路线方式计数，然后证明两

19、个计数相等。对于对于 f 使得使得c保持不变，即：保持不变，即：f *c = c 的数量用的数量用序偶序偶 (f , c)的数量决定：的数量决定： 它可以分别由它可以分别由 f 和和c两方面来求。两方面来求。第一种计数方式是第一种计数方式是： 考察考察G中的每个置换中的每个置换 f ，并计算，并计算 f 保持着色保持着色| ),(CcGfcf22不变的着色数量，然后相加所有的数量得到不变的着色数量，然后相加所有的数量得到和和。 因为因为C( f ) 是通过是通过 f 保持不变的着色集合，保持不变的着色集合，用这种计数方式计数得到：用这种计数方式计数得到：GffCCcGfcf)(|),(另一种计

20、数方式：另一种计数方式： 是考察是考察C中的每个中的每个c，计算满足：，计算满足：f *c = c的的置换置换 f 的个数，然后相加得到所有的数量的的个数，然后相加得到所有的数量的和和。对于每种着色对于每种着色 c，满足，满足f *c = c 的所有置换的所有置换 f 的的23集合就是我们定义过的稳定核集合就是我们定义过的稳定核G(c) ，因此，因此， 每种着色每种着色 c 对对和和的贡献是该着色稳定核中的贡献是该着色稳定核中的置换数：的置换数：|G(c) |，由推论：，由推论：)(GfcfGcGCcCcGfcfGcGCcGfcf)(| ),(于是，通过这种方式得到的所有着色的于是，通过这种方

21、式得到的所有着色的和和是：是：即：所有着色的稳定核中的置换数之即：所有着色的稳定核中的置换数之和和。24 但如果我们按等价类将着色归类，那么上式但如果我们按等价类将着色归类，那么上式 可以简化。在同一等价类中，有可以简化。在同一等价类中，有|G|个置换个置换对着色对着色c作用，使得每个等价类对作用，使得每个等价类对和和的总贡献是：的总贡献是：|G|。由于。由于等价类的个数等价类的个数就是就是不等价的着色数量不等价的着色数量N(G,C)，所以：，所以：证毕解得GfCfCcfCGCGNfCGfcfGGCGNCcGfcf)(1),(:)(|*),(| ),(25例：例： 将一正方形等分成将一正方形等

22、分成4格，用白、绿格，用白、绿2种颜色种颜色 着色，若经旋转可以吻合的方案算作同一着色，若经旋转可以吻合的方案算作同一个方案，个方案， 问能得到多少种不同方案的图像。问能得到多少种不同方案的图像。解：设每格有白、绿两种颜色可供选择，故所有解：设每格有白、绿两种颜色可供选择，故所有可能的图像共有可能的图像共有24种，种， 记为记为X=X1, X2, , X16。 当每个图像都绕中心轴逆时针旋转当每个图像都绕中心轴逆时针旋转0, 0,180,270时，都可得到时，都可得到X的一种排列，的一种排列，记记4种旋转置换的排列为种旋转置换的排列为G=f0, f90, f180, f270。26 | G |

23、 = 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)等形式等形式 。27 1 2 3 4 5 6 7 89 10 11 12 13 14 15 16不难求得不难求得C

24、( f0 )=16, 每种着色后旋转每种着色后旋转0 都不变，都不变， C( f90 )=2，有两种着色，有两种着色(1和和2)旋转旋转90 不变，不变，C( f180 )=4,有四种着色有四种着色(1,2,11,12)旋转旋转180 不变，不变， C( f270 )=2，有两种着色，有两种着色(1和和2)旋转旋转270 不变不变,28 故故G的不同等价类数为的不同等价类数为: 亦即在旋转吻合的前提下共有亦即在旋转吻合的前提下共有6种（不同等种（不同等价类）图案。价类）图案。例例:(循环排列计数循环排列计数)把把n个不同的对象放在一个圆个不同的对象放在一个圆上，问有多少种放法？上，问有多少种放

25、法？6424216)(),(GfCCGNGf29解：问题相当于用解：问题相当于用n种不同的颜色对正种不同的颜色对正n边形边形的角点着色，再进行的角点着色，再进行360/n种旋转置换，求种旋转置换，求旋转群的不等价的着色数。旋转群的不等价的着色数。 令令C是由对是由对正正n边形边形角点进行每种着色的颜色角点进行每种着色的颜色只出现一次的所有只出现一次的所有n!种着色方案的集合。作用种着色方案的集合。作用在在C上的循环群为：上的循环群为：,.,1210nnnnnnG30其中其中Gn中的恒等置换中的恒等置换使得使得C中的中的n!种着色不变。种着色不变。 由于在由于在C的着色中每个角点都有不同的颜色，

26、的着色中每个角点都有不同的颜色， 所以其它的置换均不能保持所以其它的置换均不能保持C中的着色，中的着色， 由定理由定理14.2.3，我们得到不等价的着色数为：，我们得到不等价的着色数为：)!1()0.00!()(),(nnnGfCCGNGf31例例: :(项链计数问题项链计数问题)用用n3种不同颜色的珠子串种不同颜色的珠子串 成一个项链，问有多少不同的方法？成一个项链，问有多少不同的方法？解：本题与上述例题几乎相同，只是项链可以两解：本题与上述例题几乎相同，只是项链可以两面翻转。设需要面翻转。设需要n个珠子串成项链，着色的集个珠子串成项链，着色的集合为合为C，其中只有恒等置换，其中只有恒等置换

27、使得使得C中的中的n!种着种着色不变色不变, 令令Gn是项链的置换群，有是项链的置换群，有n个旋转个旋转， 连同项链翻转我们共得到：连同项链翻转我们共得到： |Gn|=2n; 所以：所以：2)!1(2)0.00!(),(nnnCGN32例：考察由蓝、白、黄三种颜色的珠子中选取例：考察由蓝、白、黄三种颜色的珠子中选取 5粒串成的手镯，粒串成的手镯， 如将一只手镯经（逆时如将一只手镯经（逆时针方向）旋转而得另一只手镯视为同一手镯，针方向）旋转而得另一只手镯视为同一手镯，则称二手镯是旋转等价的。试求在旋转等价的则称二手镯是旋转等价的。试求在旋转等价的意义下不同手镯的数目。意义下不同手镯的数目。 解解

28、:设设C是不考虑旋转等价时的手镯珠子的着色，是不考虑旋转等价时的手镯珠子的着色，则则:C= c : AB，即：将，即：将A中的珠子着以中的珠子着以B中中的颜色；其中的颜色；其中A=1,2,3,4,5, B=蓝蓝,白白,黄黄。33 所以：所以：|C|=33333=35=243 将手镯的将手镯的(逆时针逆时针)旋转旋转(360/5)置换定义为置换定义为G5, 则则G5为为X上的一个置换群。上的一个置换群。 | G5 |=5 对任意手镯，若珠子颜色全同，则任意一对任意手镯，若珠子颜色全同，则任意一种旋转都会使该手镯自身变到自身，即旋转不种旋转都会使该手镯自身变到自身，即旋转不变。又当手镯中珠子粒数为

29、素数时，变。又当手镯中珠子粒数为素数时， 则不会出则不会出现不同色的手镯保持不变的情形。本例中珠子现不同色的手镯保持不变的情形。本例中珠子数量是数量是5为素数，故除了五个珠子同色外旋转都为素数，故除了五个珠子同色外旋转都34 不等价；即只有全白、全蓝及全黄这三种手镯不等价；即只有全白、全蓝及全黄这三种手镯 是旋转不变的。是旋转不变的。 故：故：C(f1)=243, C(f2)=C(f3)=C(f4)=C(f5)=3。 由由Burnside定理，在旋转等价的意义下，不同手定理，在旋转等价的意义下，不同手镯的数目应为：镯的数目应为： 5153333243)(),(55GfCCGNGf35 例：用红、蓝两色对正五边形顶点着色，例：用红、蓝两色对正五边形顶点着色，问有问有 多少不同的方法？多少不同的方法？解：一个解：一个正五边形构成的置换，可以是平面分正五边形构成的置换，可以是平面分别旋转别旋转360/5度，和以五条中垂线翻转，设置度，和以五条中垂线翻转，设置换群为：换群为