16-置换群的应用

置换群的应用离散数学第16讲上一讲内容的回顾变换和变换群置换及其表示置换群任意群与变换群同构置换群的应用置换群的应用置换群诱导的等价关系轨道轨道的大小轨道的个数-Burnside定理Burnside定理的应用相同？不同？xyztf(x,y,z,t)4个变量,可能的输入值有24个;因此,可以定义216(65,536)个不同的函数。但是，真的需要这么多种电路吗？xyx⋁yztz⋁tf(x,y,z,t)由于对称性，只要调整接入线，同样的电路可以实现不同的函数。等价类计数如果定义上述函数的集合上的关系R：函数f1,f2满足关系关系R当且仅当它们可以用同一个电路实现(只需调整接入方式，也可以用外部转相器)。显然，上述关系R是等价关系。可以用同一电路实现的所有函数包含在同一个等价类中。因此，计算需要多少种不同电路才能实现所有可能的函数问题就转化为等价类计数问题。对称在计数中的作用用6种不同颜色给正方体的六个面着色，每个面有6中选择，假如给定每个面的编号，不同的着色序列有6！(=720)个，但哪些是“真正”不同的？901801801206种3种6种8种1种因此：不同的着色有6!/(6+3+6+8+1)=30种更一般的情况如果不是每个面的着色都不同,比如有两个面是红的，如何判断两种着色是“真正”不同？设着色对象的集合是S，允许使用的颜色的集合是C(我们只考虑有限集)。一种着色方案就是一个函数f:SC。f与f2被认为“实际上”是一样的，当且仅当在所允许的变换(即前面例子中的对称旋转)下，f1能转变为f2或相反。而对称旋转即置换群的元素。我们称“(置换)群作用于S，也作用于C。”比立方体简单一点的例子3个黑珍珠和6个白珍珠能做出多少样式不同的项链？轴翻转顺时针旋转80置换群诱导的等价关系假设G是集合X上的置换群。定义X上的关系“”如下：x,yX,xygG,使得g(x)=y“”是等价关系自反性：置换群中的单位元素一定是恒等映射。对称性：由群的逆元素性保证。传递性：由群的封闭性保证。将关系所决定的等价类记为Gx:Gx={y|yX,且gG,使得g(x)=y}这样的等价类称为X上G的轨道。保持x不变的置换构成子群G中所有“将x变为y”的置换构成的集合：G(xy)={g|gG,且g(x)=y}G中所有“保持x不变”的置换的集合：Gx={g|gG,且g(x)=x}注意：Gx构成子群(只需证明封闭性)。G(xy)是Gx的右陪集：hG(xy),G(xy)=Gxh若Gxh,令=h(Gx),则xX,(x)=h((x))=h(x)=y,G(xy)若G(xy),则xX,h-1((x))=h-1(y)=x,即h-1Gx,Gxh轨道的大小子群与相应的陪集等势，因此：若yGx,|G(xy)|=|Gx|,否则|G(xy)|=0。对任意xX,x所在的轨道的大小与保持x不变的置换的个数的乘积与x无关。给定xX,构造如下的矩阵：yg√g行y列有√表示：g(x)=y对√计数：按行数：每行恰有1个√。总数为|G|。按列数，若某个yGx,则该列恰有|G(xy)|=|Gx|个√，否则为空列。所以：|Gx||Gx|=|G|yGx|Gy|值与所在轨道无关对任意的yX,若yGx,则|Gx|=|Gy|实际上，G(xy)是Gy的左陪集：即hG(xy),G(xy)=hGy若hGy,令=h(Gy),则xX,(x)=(h(x))=(y)=y,G(xy)若G(xy),则yX,(h-1(y))=(x)=y,即h-1Gy,hGy所以，对每个轨道，yGx|Gy|=|Gx||Gx|=|G|,yGx|Gy|是“一个轨道中保持各元素不变的置换的总数”轨道的个数令轨道数为t,因为每个轨道中保持各元素不变的置换的总数均为|G|,xX|Gx|=t•|G|。F(g)表示在置换g之下保持不变的x的个数。计算gG|F(g)|显然比计算xX|Gx|容易，而且：gG|F(g)|=xX|Gx|利用下列矩阵计数：xg√g行x列有√表示：g(x)=x按行算：每行√数是在置换g之下不变的x的个数。总数即gG|F(g)|按列算：每列√数是保持特定x不变的置换的个数，总数即xX|Gx|Burnside定理xX|Gx|=t•|G|gG|F(g)|=xX|Gx|於是：GggFGt)(|||1项链问题的解3个黑珍珠和6个白珍珠能做出多少样式不同的项链？|X|=84,即C93(Why?)|G|=189个旋转，9个翻转对每个翻转g,|F(g)|=4旋转0°的|F(g)|=84;旋转120°和240°的|F(g)|各为3；其它均为0。结果是：(4•9+84+3•2)/18=⑦轴翻转顺时针旋转80没有几何结构的例子3个输入的逻辑电路有多少种”真正”不同的?可能的输入共有8个(相当与珠子).可能的输出共有2个(相当于颜色).由于没有几何对称的限制,我们考虑S3上所有的置换(共6个).对于对换(12),保持不变的元素由f(0,1,x)=f(1,0,x)确定,有26个.而这样的对换共有3个.对于置换(123),(000,111)总是不变,因此函数值可以任意设定;(001,100,010)与(011,101,110)分别构成环,其函数值相等的函数将分别保持它们不变,因此,共有24个,而这样的置换有2个.恒等置换保持所有的256个函数不变.因此,不同的电路数:(256+326+224)/6=80作业Z5是“模5剩余加群”，(x)=2x(mod5)是Z5上的一个置换。G是以为生成元的循环置换群，写出G中的元素，并求出G的轨道。解13个白珍珠和3个黑珍珠的项链问题。