《组合数学讲义_POLYA定理.doc》由会员分享，可在线阅读，更多相关《组合数学讲义_POLYA定理.doc（120页珍藏版）》请在三一文库上搜索。
1、第四章 Burnside 引理 与Polya定理郝聚涛群的概念置换群循环、奇偶循环Burnside引理Plya定理举例母函数型式的Plya定理图的计数5.1 群的概念定义5.1：给定集合G和G上的二元运算(G, )，满足下列条件称为群封闭性：若a,bG，则存在cG,使得ab=c结合律成立：任意a,b,cG，有(ab)c=a(bc)（semigroup）有 单 位 元 ： 存 在 eG， 使 得 对 于 任 意 aG 满 足ae=ea=a （monoid）有逆元：任意aG，存在bG, ab=ba=e。记b=a-1（group）G=0,1,2,n-1在mod n 的加法下是群G=1,2,n-1在m
2、od n的乘法下是群 iff n是素数Dept of Computer Science and Engineering， Shanghai Jiaotong University二维欧氏空间所有刚体旋转=Ta构成群 x1 cos sin x T= T + (1) : 封闭性 : T T = T + (2) :结合律 : (TT )T = T (T T ) = T + + (3) : 单位元素 : e = T0(4) : 逆元素 : T的逆元素T- = T : y1 sin cos y = T = cos sin cos sin cos( + ) sin( + ) sin cos sin cos
3、 sin( + ) cos( + )概念有限群：元素个数有限的群无限群有限群G的元素个数叫做群的阶,记做|G|交换群（Abel群） 任意元素a,b ab=ba例: G=-1,1在乘法运算下是一个群封闭性:(1)(-1)=-1;(1)(1)=1;(-1)(1)=1,(-1)(-1)=1;结合性：显然单位元素：e=1逆元素 由于(1)(1)=1 (-1)(-1)=1故（-1）-1 =1，（-1）-1=-1群的性质定理：群的单位元是唯一的证：假设有两个单位元e1,e2e1e2=e2e1e2=e1e1 = e2定理定理 : ab = ac b = c, ba = ca b = c11定理 : G中的每
4、一个元素的逆元素是唯一的1 1 11 1 1定义 :设G是群, H是G的子群,若H在G的原来定义的运算下也成群,则称H为G的子群( ) ( )1a ab a a b b= =( ) ( )1a ac a b c c= =定理 .: (abc.lmn) -1 1 1 1n m l c b a= (abc.lmn) .1 1 1n m l c b a e= 置换群置换群是最重要的有限群，所有的有限群都可以用之表示。置换：1,n到自身的1-1变换，例如n阶置换，其中a1a2an是1,n中元素的一个排列n阶置换共有n!个例5.2置换乘法Dept of Computer Science and Engi
5、neering， Shanghai Jiaotong University置换群1,n上的所有n阶置换在上面的乘法定义下是一个群。验证是否满足群的性质Dept of Computer Science and Engineering， Shanghai Jiaotong University例：圆圈上装有A，B，C三颗珠子，正好构成等边三角形，（1）绕过圆心垂直于圆平面的轴，沿反时针方向旋转0，120，240；（2）沿过圆心及A点的轴线翻转180度。经过1，2变换A，B，C三颗珠子两两重合，但顶点交换位置。以1代A，2代B，3代C1 2 3 1 2 3 1 2 31 2 3 2 3 1 3 1
6、2 1 2 3 1 2 3 1 2 31 3 2 3 2 1 2 1 3这六个置换是一个群=1p= 2p= 3p=4p= 5p= 6p正n边形的对称群例5.3 等边三角形的运动群。绕中心转动120度(两个)、不动（一个）、绕对称轴翻转（三个），运动群的个数有6个。正方形的运动群。绕中心转动90度(三个)、不动（一个）、绕对称轴翻转（四个）对于任意的n=3，可得到正n边形的对称群（运动群）：n个旋转：n, n2, , nn-1，其中n视为圆的360/n度的旋转， n2视为圆的2(360/n)度的旋转n个翻转： 1, 2, , nDept of Computer Science and Engin
7、eering， Shanghai Jiaotong University正n边形的n个翻转若n是偶数，则有n/2个关于对角点的翻转， n/2个关于对边中线的翻转；若n是奇数，则有n个顶点与其对边中点的连线的的翻转；Dept of Computer Science and Engineering， Shanghai Jiaotong Universityn阶对称群1,n上的所有置换(共n!个)构成一个群，称为n阶对称群，记做Sn.n个文字的对称群注意：一般说1,n上的一个置换群，不一定是指Sn，但一定是Sn的某一个子群。Dept of Computer Science and Engineeri
8、ng， Shanghai Jiaotong University循环、奇循环与偶循环例5.4 1 2 3 4 5 4 3 1 5 2 a a2a2 . am1 am a3 . am a1 1 3 1 52 3 4 5 1 2 5 4 2 3 4 5 2 3 1 4 (a1a2am)=(a2a3ama1)=(ama1am-1)有m种表示方法。Dept of Computer Science and Engineering， Shanghai Jiaotong University置换的循环表示： (a1, a2 ,., am ) = 1 = (1 4 5 2 3) = (1 3 2)o (4 5
9、) = (1 5 4)o (2)o (3)1 2 3 2 3 11 2 31 2 31 2 3 1 2 3 2 3 1 2 3 1 2 3 1 1 2 3=p(1 2 )= 3 =p=(1)(2)(3)=1 2 31 2 3 1 2 3 2 1 3 3 2 1 3 2 1(1 2)(1 3) =(1 2 3)=定理5.2: 任一循环都可以表示为对换的积。例5.5：(1 2 n)=(1 2)(1 3) (1 n)= (2 3) (2 4) (2 n) (2 1) 表示不唯一。注：分解成对换的形式不唯一，但对换个数的奇偶性唯一。任一置换表示成对换的个数的奇偶性是唯一的置换分成两大类：奇置换与偶置换
10、。循环长度减1的奇偶性即置换奇偶性定理：Sn中所有偶置换构成一阶为(n!)/2的子群称为交错群，记做AnDept of Computer Science and Engineering， Shanghai Jiaotong University证明 :1 2 .n 1 2.n An非空(1)封闭性 : p1, p2是偶置换,则p3 = p1p2也是偶置换(2)结合律 : 置换群的结合律成立(3)单位元素 : 置换群的单位元素本身就是偶置换(4)逆元素 : (i, k )的逆元素为(i, k ), p = (i1, j1)(i2 , j2 ).(ik , jk )的逆元素p 1 = (ik ,
11、jk ).(i2 , j2 )(i1, j1)pp 1 = (i1, j1)(i2 , j2 ).(ik , jk )(ik , jk ).(i2 , j2 )(i1, j1 )= (1)(2).(n)Bn = S n An表示奇置换任取其中一个换位(i, j),对A n的任一置换p,则(i, j) p就是奇置换A n Bn ,同理可证 Bn A n故 A n =12n! = (1)(2).(n)故先证明An是Sn的子群.首先单位元共轭类先观察S3, A3, 以增加感性认识：S3=(1)(2)(3),(23),(12),(13),(123),(132).A3=(1)(2)(3),(123),(
12、132).观察S4, A4,S4=(1)(2)(3)(4),(12),(13),(14),(23),(24),(34),(123),(124),(132),(134),(142),(143),(234),(243),(1234),(1243),(1324),(1342),(1423),(1432),(12)(34),(13)(24),(14)(23).A4=(1)(2)(3)(4),(123),(124),(132),(134),(142),(143),(234),(243),(12)(34),(13)(24),(14)(23).Dept of Computer Science and Eng
13、ineering， Shanghai Jiaotong UniversitySn中P的循环格式(1)C1(2)C2(n)Cn,其中 Ci :长度为i 的循环的个数例5.6 S4中置换(123)= (123) (4)，其循环格式为(1)1(2)0 (3)1(4)0Sn中有相同格式的置换全体构成一个共轭类。例5.7 S4中置(123),(124),(132),(134),(142),(143),(234),(243)具有相同的循环格式(1)1(2)0 (3)1(4)0Dept of Computer Science and Engineering， Shanghai Jiaotong Univer
14、sity共轭类计数定理5.3: Sn中属(1)C1(2)C2(n)Cn共轭类的元素的个数为n!C1!C2!. Cn!1C1 2C2 . nCn证：设给定循环结构 (1)C1(2)C2(n)Cn一个长度为k的循环有k种表示，Ck个长度为k的循环有Ck!kCk种表示.1,2,n的全排列共有n!个，给定一个排列，装入格式得一置换，除以前面的重复度得n!C1!C2!. Cn!1C1 2C2 . nCn个不同的置换.Dept of Computer Science and Engineering， Shanghai Jiaotong University例5.8 S4中(2)2共轭类有4!/(2!22)
15、=3(1)1(3)1共轭类有4!/(C1!C3!1C13C3)=8(1)1(2)1共轭类有4!/(C1!C2!1C12C2)=6Dept of Computer Science and Engineering， Shanghai Jiaotong Universityk 不动置换类定义：设G是1,n上的一个置换群，G Sn对于k1,n，G中使k保持不变的置换全体，称为k不动置换类，记做Zk。定理5.4 置换群G的k不动置换类Zk是G的一个子群。封闭性：结合性：自然。有单位元：G的单位元属于Zk。有逆元：PZk,则, P-1Zk.例5.9 设G=(1)(2)(3)(4), (12), (3 4)
16、, (1 2)(3 4)。G中有因子(k）的置换的全体对于A4, 可得 Z1=e, (2 3 4), (2 4 3), Z2=e, (1 3 4), (1 4 3)Z3=e, (1 2 4), (1 4 2), Z4=e, (1 2 3), (1 3 2)Dept of Computer Science and Engineering， Shanghai Jiaotong UniversityZ1=Z2=e, (3 4), Z3=Z4=e, (1 2)；等价类一般1,n上置换群G将1,n分成若干等价类，若在G的作用下，i变为了j，我们称i和j属于同一等价类：满足等价类的3个条件(a)自反性;
17、(b)对称性; (c)传递性。该等价类也称为G作用下的轨迹。例5.9 设G=(1)(2)(3)(4), (12), (3 4), (1 2)(3 4)。其中，1和2属于同一等价类，3和4属于同一等价类。burnside定理：等价类个数Dept of Computer Science and Engineering， Shanghai Jiaotong University数k所属的等价类记为:EkE1=E2 =1,2,E3=E4=3,4定理|Ek|Zk|=|G|,k=1,2n证明 : 若 E k = l,不失一般性,设E k = a1 (= k ), a2 ,., al ,a1 (= k ),
18、 a1, a2 ,., al是l个不超过n的正整数,且各不想等.由于a2 ,., al属于同一等价类,故存在属于G的置换pi使得pi即置换pi使得数k变为等价类中的aiik a i l, 1,2,.=P = p1, p2 ,. pl 是属于群G的置换的集合,但是不是一个群.作G i = Z k pi , i = 1,2,.l.由于故p p jpp j = p j Z k p j即数k在p Z k p j的作用下变为a jGi = Z k P的元素属于G,而且当i j时, G i I G j = .故G1 + G 2 + .G l G(+不相交集合的并 )k kZ k a jk a ji另一方面
19、，凡属于G的任一置换p,有pjpG p 1pp j 11p Z k p jp是G的任意元素,故有 : G Z k p1 + Z k p2 + .Z k pl由上面两式 : G =| Z k p1 | + | Z k p2 | +. | Z k pl |l项= | Z k | +. + Z k = l Z k=| Ek | Z k |k a j依据元素k的等价类,存在Pj G,使得k a j .所以有 :pk a j k即k kj依据Z k定义,有 pp Z k64474485.2 Burnside引理设G=p1,p2,pg是目标集1,n上的置换群。每个置换都写成不相交循环的乘积。G将1,n分成
20、l个等价类。c1(pk)是在置换pk的作用下不动点的个数，也就是长度为1的循环的个数。Burnside引理：等价类个数：l=c1(p1)+c1(p2)+c1(pg)/|G|例如，G=e, (1 2), (3 4), (1 2)(3 4).c1(g1)=4,c1(g2)=2,c1(g3)=2,c1(g4)=0.l=4+2+2+0/4=2.以本例列表分析：j行之和c1(pj), k列之和|Zk|总和 c1(pj) |Zk|Dept of Computer Science and Engineering， Shanghai Jiaotong UniversityBurnside引理证明p Z0 k
21、l, (l k证明：表中元素定义为nk =1jk= C1( p j ),gj =1jk= Z k设在G作用下， 1,n分成l个等价类。1,n=E1+E2+El.若j,i同属一个等价类则Ei=Ej,|Ei|=|Ej|因|Ei|Zi|=|G|,故|Zi|=|Zj|.i E iZ i = Z i E in gk =1 j =1jk=nk =1k| =lt =1 i E iZ i =lt =1Z i E i=lt =1= l Gg nj =1 k =1jkgj =11Ggj =1Dept of Computer Science and Engineering， Shanghai Jiaotong Un
22、iversity1,k j k S jk = p Zj k S S S | Z G S= C 1 ( p j ) l = C 1 ( p j )123456789 10 11 12 13 14 15 16例5.10 一正方形分成4格，2种着色，有多少种方案？图象：看上去不同的图形。方案：经过平面转动相同的图象算同一方案。图象数总是大于方案数。不动 ：p1=(1)(2)(16)逆时针转90：p2=(1)(2)(3456)(78910)(11 12)(13 14 15 16)顺时针转90：p3=(1)(2)(6543)(10987)(11 12)(16 15 14 13)转180：p4=(1)(2
23、)(35)(46)(79)(810)(11) (12)(13 15)(14 16所以，总共有(16+2+2+4)/4=6(种方案)Dept of Computer Science and Engineering， Shanghai Jiaotong University一个圆环,按顺时针方向0,90,180,270度位置上装一个红或蓝的珠子,问有多少种不同的等价类.即有多少种不同的方案?刚体运动使之吻合的算一种方案.这个问题可以看作是正方形的四方格的情况,如图(右图所示),但四方形是透明的玻璃板,用红蓝两色进行着色,问有多少种着色方案?对应的置换群除了和前例一样的p1,p2,p3,p4之外，还
24、包含：（5）沿xx翻转180度，对应的置换：P5=(c1)(c2)(c3c6)(c4c5)(c7c10)(c8c9)(c11c12)(c13)(c15)(c14c16)c1(p5)=4(6)沿yy轴翻转180，对应有置换：P6=(c1)(c2)(c3c4)(c5c6)(c7c8)(c9c10)(c11c12)(c13c15)(c14)(c16)c1(p6)=4（7）沿对角线13翻转180度，对应置换为：P7=(c1)(c2)(c3)(c4c6)(c5)(c7)(c8c10)(c9)(c11)(c12)(c13c14)(c15)(c16)c1(p7)=8(8)沿对角线24翻转180度，对应的置换
25、：P8=(c1)(c2)(c3c5)(c4)(c6)(c7c9)(c8)(c10)(c11)(c12)(c13c16)(c14c15)c1(p8)=8根据Burnside公式，不同的等价类为：l=1/8*16+2+4+2+4+4+8+8=66种不同的方案和图（左）一致，它的含义却不尽相同，包括各种类型的翻转Plya定理：设G=p1,p2,pg是上的一个置换群，C(pk)是置换pk的循环的个数，用M中的颜色对中的元素着色，1 1 2 gG证：对的n个目标用m种颜色，着色的图象集为M, |M|=|M|=mnG的每一个元素pi是上的一个置换，也对应了G在M上的一个置换pi, 这样GG,T: pi p
26、i ,在pi的作用下不动图象的个数C1(pi)等于pi的同一i因而在G的作用下，M(图象)的等价类的个数。1 1 C ( p1 ) C ( p2 )| G+ . + mC ( pg )Dept of Computer Science and Engineering， Shanghai Jiaotong UniversitymC ( p ) + mC ( p ) + . + mC ( p )着色方案数为循环中的目标都着相同色的方案的个数。即 C1( pi ) = mC ( p ) 。| C1( p1 ) + C1( p2 ) + . + C1( pg ) = G m+ ml =例：长为6的透明的
27、方格，用红、蓝、黄、绿4种颜色进行染色，试问有多少种不同的方案？问题相当于用r,b,y,g构成长为n的字符串，将从左向右的字符顺序和从右向左的字符顺序看作是相同的，例如，yggrbr和rbrggy看作是相同的。群G：1 2 .6 1 2 3 4 5 6 1 2.6 6 5 4 3 2 1根据Polya定理,不同的方案数为N =123 = (1 6) (2 5)(3 4) p2 = p1 = (46 + 4 )用3个红珠子,2个蓝色珠子镶嵌在圆环上(如图所示),试问有多少种不同的方案G:(1)(2)(3)(4)(5),(12345),(13524)(14253),(15432),(1)(25)(
28、34),(2)(13)(45),(3)(15)(34),(4)(12)(35),(5)(14)(23)对应于g0=(1)(2)(3)(4)(5),用3红2蓝镶嵌可有c(5,3)=10种方案，在g0作用下变为自身。对应于（12345）等4个(5)1格式的方案数为0。对应于(1)1(2)2格式的方案数为2，故N=1/10*10+5*2=2例：图(a)中v1，v2，v3，是圆圈上3等分点，用红、蓝、绿3种颜色的珠子镶上，试问有几种不同的方案？解：图(a)可以分别绕圆圈的中心旋转0，120，240，以及以过顶点1的垂直于其他两顶点的连线的垂直线为轴翻转，得群：G=(v1)(v2)(v3),(v1v2v
29、3),(v3v2v1),(v1)(v2v3),(v2)(v1v3),(v3)(v1v2)故不同的方案数为m=1/6*33+2*3+3*32=1010种方案见图(b)例：求3个布尔变量x1,x2,x3的布尔装置有多少种不同的结构3个变量的布尔函数有28=256个。但布尔函数f(x1,x2,x3)装置可以通过改变输入端的顺序而得到，不必改变装置本身的内容。3个输入端的变换群H为：h1=(x1)(x2)(x3),h2=(x1x2x3),h3=(x3x2x1),h4=(x1)(x2x3),h5=(x2)(x1x3),h6=(x3)(x1x2)3个布尔变量x1,x2,x3构成的3位二进制数x1x2x3的
30、状态有：a0=000, a1=001,a2=010,a3=011,a4=100,a5=101, a6=110, a7=111,在以h2=(x1x2x3)的作用下 即h2=(x1x2x3)对应于置换：为例 a0 a1 a2 a3 a4 a5 a6 a7 a a a a a a aa3=011-110=a6 = (a0 )(a1a2a4 )(a3 a6a5 )(a7 )a4-a1a5-a3a6-a5a7- a7P2=a0=000-000=a0a1=001-010=a22p =a2=010-100=a4 0 2 4 6 1 3 5 7a 若hi pi , i = 1,2,.6p1 = (a0 )(a
31、1 )(a2 )(a3 )(a4 )(a5 )(a6 )(a7 )p2 = (a0 )(a1a2a4 )(a3a6a5 )(a7 )p3 = (a0 )(a1a4a2 )(a3a5a6 )(a7 )p4 = (a0 )(a1a2 )(a3 )(a4 )(a5a6 )(a7 )p5 = (a0 )(a1a4 )(a2 )(a3a6 )(a5 )(a7 )p6 = (a0 )(a1 )(a2a4 )(a3a5 )(a6 )(a7 )求不同布尔函数装置的问题,相当于求服从群G的变换的8个顶点a0 , a1, a2 , a3 , a4a5 , a6 , a7用两种不同颜色(相当于布尔函数0,1状态)的
32、方案数,根据Polya定理应有1 46不同的结构不适256种,而是80种,其它的可通过输入端的顺序而得到(2 3 2 2 2 ) 80m 68= + + =例5.10 一正方形分成4格，2种着色，有多少种方案？12四个顶点1,2,3,4的置换群：43不动 ：p1=(1)(2)(3)(4)逆时针转90：p2=(1234)顺时针转90：p3=(1432)转180：p4=(13)(24)所以，总共有(21+21+22+24)/4=6(种方案)Dept of Computer Science and Engineering， Shanghai Jiaotong University例5.11 ：等边三
33、角形的3个顶点用红，兰，绿3着色，有多少种方案？解：在3维空间考虑，3顶点的置换群S3。变换包括：1. 不动置换：(1) (2) (3)2. 绕中心逆时针旋转120度： ( 1 3 2)3. 绕中心逆时针旋转240度： ( 1 2 3)A4. 绕AE中线翻转： (1) (2 3)BC5. 绕BE中线翻转： (2) (1 3)6. 绕CE中线翻转： (3) (1 2)(3)1 2个; (1)1(2)1 3个; (1)3 1个;所以方案数为：l=(231+332+33)/6=10Dept of Computer Science and Engineering， Shanghai Jiaotong
34、University例5.12 正6面体的6个面分别用红，蓝两种颜色着色，有多少方案？1解：正6面体的转动群用面的置换表示（共24个变换）：43652up: 1Down: 6不动置换：(1) (2) (3) (4)(5)(6) 格式(1)6right: 2front: 3left: 4back: 5面心-面心：沿AB轴旋转90度，-90度，180度，A1(1) (6) (5432)格式(1)2(4)1 (三个)452(1) (6) (2345) 格式(1)2(4)1 (三个)36(1) (6) (24) (35) 格式(1)2(2)2 (三个)up: 1right: 2front: 3BDown: 6left: 4back: 5Dept of Comp