16-置换群的应用ppt课件

1、置换群的运用置换群的运用离散数学 第16讲上一讲内容的回想上一讲内容的回想l变换和变换群l置换及其表示l置换群l恣意群与变换群同构l置换群的运用置换群的运用置换群的运用l置换群诱导的等价关系l轨道l轨道的大小l轨道的个数-Burnside定理lBurnside定理的运用一样？不同？一样？不同？xyztf(x,y,z,t)4个变量, 能够的输入值有24个;因此, 可以定义216(65,536)个不同的函数。但是，真的需求这么多种电路吗？xyxyztztf(x,y,z,t)由于对称性，只需调整接入线，同样的电路可以实现不同的函数。等价类计数等价类计数l假设定义上述函数的集合上的关系R：函数f1,

2、f2满足关系关系R当且仅当它们可以用同一个电路实现(只需调整接入方式，也可以用外部转相器)。l显然，上述关系R是等价关系。l可以用同一电路实现的一切函数包含在同一个等价类中。l因此，计算需求多少种不同电路才干实现一切能够的函数问题就转化为等价类计数问题。对称在计数中的作用对称在计数中的作用用6种不同颜色给正方体的六个面着色，每个面有6中选择，假设给定每个面的编号，不同的着色序列有6！(=720)个，但哪些是“真正不同的？901801801206种3种6种8种1种因此：不同的着色有6!/(6+3+6+8+1)=30种更普通的情况更普通的情况l假设不是每个面的着色都不同, 比如有两个面是红的，如何

3、判别两种着色是“真正不同？l设着色对象的集合是S，允许运用的颜色的集合是C(我们只思索有限集)。一种着色方案就是一个函数f:SC。f与f2被以为“实践上是一样的，当且仅当在所允许的变换(即前面例子中的对称旋转)下， f1能转变为f2或相反。l而对称旋转即置换群的元素。我们称“(置换)群作用于S，也作用于C。比立方体简单一点的例子比立方体简单一点的例子l3个黑珍珠和6个白珍珠能做出多少款式不同的项链？轴翻转顺时针旋转80置换群诱导的等价关系置换群诱导的等价关系 l假设G是集合X上的置换群。定义X上的关系“如下：lx,yX, xy gG, 使得g(x)=y l“是等价关系l自反性：置换群中的单位元

4、素一定是恒等映射。l对称性：由群的逆元素性保证。l传送性：由群的封锁性保证。l将关系所决议的等价类记为Gx: l Gx=y|yX, 且gG, 使得g(x)=yl这样的等价类称为X上G的轨道。 坚持坚持x不变的置换构成子群不变的置换构成子群lG中一切“将x变为y的置换构成的集合：l G(xy) = g|gG, 且g(x)=ylG中一切“坚持x不变的置换的集合：l Gx=g|gG, 且g(x)=xl留意：Gx构成子群(只需证明封锁性)。lG(xy)是Gx的右陪集：hG(xy), G(xy)=Gxhl假设Gxh, 令=h(Gx), l 那么xX, (x) = h(x) = h(x) =y, G(xy

5、)l假设 G(xy), l 那么xX, h-1(x)=h-1(y)=x, 即h-1Gx, Gxhl 轨道的大小轨道的大小l子群与相应的陪集等势，因此：假设yGx, |G(xy)|=|Gx|, 否那么|G(xy)|=0。l对恣意xX, x所在的轨道的大小与坚持x不变的置换的个数的乘积与x无关。l给定xX, 构造如下的矩阵：l y l l g g行y列有表示：g(x)=yl l对计数：按行数：每行恰有1个。总数为|G|。按列数，假设某个yGx, 那么该列恰有|G(xy)|=|Gx|个，否那么为空列。所以：l |Gx|Gx|=|G| y Gx|Gy|值与所在轨道无关值与所在轨道无关l对恣意的yX,

6、假设yGx, 那么|Gx|=|Gy|l实践上，G(xy)是Gy的左陪集：即hG(xy), G(xy)= hGyl假设hGy, 令=h (Gy), 那么xX, (x)=(h(x)=(y)=y, G(xy)l假 设 G ( x y ) , 那 么 y X , ( h -1(y)=(x)=y, 即h-1Gy, hGyl所以，对每个轨道，yGx|Gy|=|Gx|Gx|=|G|, l yGx|Gy|是“一个轨道中坚持各元素不变的置换的总数轨道的个数轨道的个数 l令轨道数为t, 由于每个轨道中坚持各元素不变的置换的总数均为|G|, xX|Gx| = t|G|。lF(g)表示在置换g之下坚持不变的x的个数。

7、计算gG|F(g)|显然比计算xX|Gx|容易，而且： l gG|F(g)| = xX|Gx|l利用以下矩阵计数：l x llg g行x列有表示：g(x)=xl l按行算：每行数是在置换g之下不变的x的个数。总数即gG|F(g)|l按列算：每列数是坚持特定x不变的置换的个数，总数即xX|Gx|Burnside定理定理lxX|Gx| = t|G|lgG|F(g)| = xX|Gx|l於是：l GggFGt)(|1 项链问题的解项链问题的解l3个黑珍珠和个黑珍珠和6个白珍珠能做出多少款式不同的项链？个白珍珠能做出多少款式不同的项链？l|X|=84, 即即C93 (Why?)l|G|=18 9个旋转

8、，个旋转，9个翻转个翻转l对每个翻转对每个翻转g, |F(g)|=4l旋转旋转0的的|F(g)|=84; 旋转旋转120 和和240 的的|F(g)| 各为各为3；l 其它均为其它均为0。l结果是：结果是：l(49+84+32)/18l = 轴翻转顺 时 针 旋 转80没有几何构造的例子没有几何构造的例子l3个输入的逻辑电路有多少种真正不同的?l能够的输入共有8个(相当与珠子).l能够的输出共有2个(相当于颜色).l由于没有几何对称的限制, 我们思索S3上一切的置换(共6个).l对于对换(1 2), 坚持不变的元素由f (0,1,x) = f(1,0,x)确定, 有26个. 而这样的对换共有3个.l对于置换(1 2 3), (000, 111)总是不变, 因此函数值可以恣意设定; (001, 100, 010)与(011, 101, 110)分别构成环, 其函数值相等的函数将分别坚持它们不变, 因此,共有24个, 而这样的置换有2个.l恒等置换坚持一切