组合数学第四章

第四章Pölya定理1.群的定义及性质定义：设G是一个非空集合，GGG:是G中运算，如果满足：（1）封闭律GabGba,,（2）结合律)(),(,,,,cbacbaGcba（3）有单位元,Ge对aaeeaGa,（4）有逆元eabbaGbGa,,则称G为一个群。例1：整数加群，有理数加群，实数加群，复数加群。例2：非零实数乘法群。例3：一般线性群与特殊线性群例4：二维空间中变换群（1）群中单位元是唯一的；（2）每个元的逆元是唯一的；（3）群中消去律成立；（4）一般情况下，交换律不成立（5）Abel群；（6）子群2.置换群n次对称群级全排列为一个niiiiiiinSnnn21321321则nS关于置换的合成构成一个群。1221212122Sn213321,132321,231321,123321,312321,32132133Sn32144321,,43124321,4321432144Sn24!46!32!2432SSS令12332131232121pp13232112332131232121pp12332131232112332112ppnSpppp1221非交换群置换群：nS的每个子群叫做n阶置换群。3S的子群：312321,321321,32132121HH,231321,321321,123321,32132143HH35SH置换群的表示：置换表示：将n元置换群中每个元素用置换表示出来。213321,132321,231321,123321,312321,3213213S轮换表示（循环表示）如果置换将1a变到2a，将2a变到,,3a将1ka变到ka，将ka变到1a，而保持其他元素不动，则称该置换为一个长为k的轮换（循环，）记为（kaaa21）。比如)14523(2513454321)145(15324543211长度为1的轮换是恒等置换，记为（1），或（2），…，（n）.2长度为2的轮换叫做对换，对换就是将其中两个元素对调的置换。定理：任意一个置换在不考虑轮换顺序情况下，均可唯一地表示成若干互不相交循环乘积。)}132(),123(),23(),13(),12(),1{(3S),234(),143(),142(),134(),132(),124(),123(),34(),24(),23(),14(),13(),12(),1{(4S)}23)(14(),24)(13(),34)(12(),1432(),1423(),1342(),1324(),1243(),1234(),243(对换表示任意一个轮换均可表示成对换的乘积，在一般情况下，这种表示不唯一。)())(()(1312121kkaaaaaaaaa定理：每个置换均可表示成若干对换的乘积，一般情况下，这种表示法是不唯一的，但对换个数的奇偶性是唯一的。)15)(12)(15()25(2435154321奇置换：恰好用奇数个对换的乘积表示的置换。偶置换：恰好用偶数个对换的乘积表示的置换。令nAn{元集上全体偶置换}，则nA构成nS的一个子子群，称nA为n次交错群，可知!21nAn)}132(),123(),1{(3A)}23)(14(),24)(13(),34)(12(),243(),234(),143(),142(),134(),132(),124(),123(),1{(4A3.Burnside引理)}132(),123(),23(),13(),12(),1{(3S元素格式)3()2()1()3)(2)(1(321321)1(3)3()2()1()3)(12(312321)12(11)3()2()1()2)(13(123321)13(11)3()2()1()23)(1(231321)23(111)3()2()1()123(132321)123(1)3()2()1()123(213321)123(即n次对称群中每个置换均有如下表示格式0)()2()1(21iccccnn其中kck)(表示置换的轮换表示中长度为k的循环出现个数。定义：设1p和2p是nS中两个置换，如果1p与2p具有相同的格式，则称1p与2p共轭。定理：nS中格式为ncccn)()2()1(21的共轭类中元素的个数为ncccnncccn2121!!!!21证明：ncccn)()2()1(21格式为nnccccc)()())(()())((22112全体n级全排列为n!重复的排列有（1）每个k循环)(21kaaa重复k次，共kck次，（2）kc个k循环顺序无关，重复,!kc共有ncccnncccn2121!!!!21定义：设G是一个n元置换群，即nSG，令kZ是G中使k保持不变的置换的全体，则kZ构成G的一个子群，称为k不动置换类。比如四次交错群),243(),234(),143(),142(),134(),132(),124(),123(),1{(4A)}23)(14(),24)(13(),34)(12(中，)}143(),134(),2{()},243(),234(),1{(21ZZ)}132(),123(),4{()},142(),124(),3{(43ZZ定义：设G是一个n元置换群，},,2,1{,nji，如果存在置换Gp，使得)(ipj，则称i与j等价。令GnA},,,3,2,1{为一个n元置换，对Aba,，)(,bpaGpba与依等价关系，可以将A划分为若干互不相交等价类的并集，kkEA其中kE{所有与k等价的元素}定理：GZEkkpf：不妨设AaaakaaaaEiJilk,,},,,{121。由于对每个i而言，,~)1(1iaali故存在Gpi，使得)(1apaii令lipZGik,,2,11则jiGGjiGGGGl21221GGGG故,221GGGG于是kkEZGGGG221Burnside引理：设G是},,2,1{nN上置换群，G在N上可引出不同的等价类，其不同等价类的个数为：)]()()([112111gacacacGl其中)(},,,{121kgacaaaG表示置换ka中1阶循环个数。Pf:GnN},,,3,2,1{为N上一个置换群，即,nSG设},,,{21gaaaG对每个GZNkk{,保持k不动的置换），NEk{中与k等价的元素}，lk,,2,1则GEZkk再令时当时当kjkjjkZaZaS10则knkjgjjknkgjkjkgjjjknkZacSZSacS11111111)(,),(又GlZEZZiilikEkliknkl111故)(111jgjacGl。例1：一正方形均分成4个格子，用两种颜色对4个格子着色，问能得到多少种不同的图象！经过旋转使之吻合的两种方案算是同一方案。解：藉不考虑旋转，则有16种方案1615321,,,,,ccccc旋转情况有四种：1旋转0度，)())((16211cccp2旋转90度，))()()()()((161514131211109876543212ccccccccccccccccp3旋转180度，))()()()()()()()()((161415131211108976453213ccccccccccccccccp4旋转270度，))()()()()((131415161211789103456214ccccccccccccccccp故6)24216(41l4.Pölya定理背景：设有n个对象，G是这n个对象上的置换群，今用m种颜色涂染这n个对象，每个对象涂一种颜色，当一种染色方案在G的作用下变为另一种方案，则这两方案当作同一种方案，问有多少种集色方案。Pölya定理设G是n个对象的一个置换群，用m种颜色涂染这n个对象，则不同染色方案数为)()()(0211acacacmmmGl，其中)(},,,,{21kgacaaaG为置换ka的循环节数。Pf:假定n个对象用m种颜色进行涂色所得的方案集合为S，则nmS。G的每一个元素ja对应于n个对象的一个排列，也对应了s中nm个涂色方案的一个排列，记为ja，从而GG，GG，进一步)(1)(jacjmac故)()()(112111gacacacGl)()()(211gacacacmmmG例1：321vvv是一等边三角形，用红，蓝，绿三色对顶点进行着色，问有几种不同方案。1v)})((),(),(),)()({(321123321321vvvvvvvvvvvvG2v3v)})((),)((213312vvvvvv103332361213m例2：求三个布尔变量321,,xxx的布尔函数装置有多少种不同的结构？1x2x)(321xxxf3x解：输入端变换群},,,,,{654321hhhhhhH)(),(),)()((123332123211xxxhxxxhxxxh))((),)((),)((213631253214xxxhxxxhxxxh321xxx的状态111,010,001,0007210aaaa用H作用在输入端321xxx上等价于某个群作用在状态上},,,,,{654321ppppppG))()()()()()()((765432101aaaaaaaap))()()((756342102aaaaaaaap))()()((765324103aaaaaaaap))()()()()((765432104aaaaaaaap))()()()()((756324105aaaaaaaap))()()()()((765342106aaaaaaaap故80)22232(61468l5.母函数型的Pölya定理方案数)()()(111gacacacmmmGl方案)()(2)(1)()(2)(1222121[1acnacacacnacacssssssGPn21n21])()(2)(121gnggacnacacsss其中nkbbbskmkkk,,2,121，这里},,,{21mbbb为m种不同颜色。例1：有三种不同颜色的珠子，把它装成四个珠子的顶链问有哪些方案？