置换群在计数中的应用2021完整版课件.ppt

1、PART置换群在计数中的应用PART1一的基本概念定义1 任一集合A到自身的映射都叫做的A一个变换，如果A是有限集且变换是一一变换（双射），那么这个变换为A的一个置换。有限集合A的若干个置换若作成群，就叫做置换群。含有n个元素的有限群A的全体置换作成的群，叫做n次对称群。通常记为Sn。大家应该知道什么是变换群吧？封闭性、可结合、有单位元、存在逆元321321213321132321g g行x列有表示：g(x)=x传递性：由群的封闭性保证。将关系所决定的等价类记为Gx:而对称旋转即置换群的元素。|X|=84,即C93(Why?)G(xy)=g|gG,且g(x)=yx 定义X上的关系“”如下：我们

2、称“(置换)群作用于S，也作用于C。其实我们看一下群与对称更好额给定xX,构造如下的矩阵：定义1 任一集合A到自身的映射都叫做的A一个而对称旋转即置换群的元素。因此：不同的着色有6!/(6+3+6+8+1)=30种x,yX,xy gG,使得g(x)=y对每个翻转g,|F(g)|=4p119PART2用6种不同颜色给正方体的六个面着色，每个面有6中选择，假如给定每个面的编号，不同的着色序列有6！(=720)个，但哪些是“真正真正”不同的？因此：不同的着色有6!/(6+3+6+8+1)=30种901801801206种3种6种8种1种其实我并没有看太明白其实我们看一下群与对称更好额比立方体简单一点

3、的例子比立方体简单一点的例子3个黑珍珠和6个白珍珠能做出多少样式不同的项链？轴翻转顺时针旋转80置换群诱导的等价关系置换群诱导的等价关系 l假设G是集合X上的置换群。定义X上的关系“”如下：x,y X,x y g G,使得使得g(x)=y l“”是等价关系l自反性：置换群中的单位元素一定是恒等映射。l对称性：由群的逆元素性保证。l传递性：由群的封闭性保证。l将关系所决定的等价类记为Gx:Gx=y|y X,且且 g G,使得使得g(x)=y这样的等价类称为X上G的轨道轨道。保持保持x不变的置换构成子群不变的置换构成子群lG中所有“将将x变为变为y”的置换的置换构成的集合：G(xy)=g|gG,且

4、g(x)=ylG中所有“保持x不变”的置换的集合：Gx=g|gG,且g(x)=xl注意：Gx构成子群(只需证明封闭性)。lG(xy)是Gx的右陪集：hG(xy),G(xy)=Gxhl若Gxh,令=h(Gx),则xX,(x)=h(x)=h(x)=y,G(xy)l若 G(xy),则xX,h-1(x)=h-1(y)=x,即h-1Gx,Gxh 轨道的大小轨道的大小l子群与相应的陪集等势，因此：若yGx,|G(xy)|=|Gx|,否则|G(xy)|=0。l对任意xX,x所在的轨道的大小与保持x不变的置换的个数的乘积与x无关。l给定xX,构造如下的矩阵：y g g行y列有表示：g(x)=y l对计数：按行

5、数：每行恰有1个。总数为|G|。按列数，若某个yGx,则该列恰有|G(xy)|=|Gx|个，否则为空列。所以：|Gx|Gx|=|G|y Gx|Gy|值与所在轨道无关值与所在轨道无关l对任意的yX,若yGx,则|Gx|=|Gy|l实 际 上，G(x y)是 Gy的 左 陪 集：即hG(xy),G(xy)=hGyl若 h Gy,令 =h (Gy),则 x X,(x)=(h(x)=(y)=y,G(xy)l若 G(xy),则yX,(h-1(y)=(x)=y,即h-1Gy,hGyl所以，对每个轨道，yGx|Gy|=|Gx|Gx|=|G|,yGx|Gy|是“一个轨道中保持各元素不变的置换的总数一个轨道中保

6、持各元素不变的置换的总数”轨道的个数轨道的个数 l令轨道数为t,因为每个轨道中保持各元素不变的置换的总数均为|G|,xX|Gx|=t|G|。lF(g)表示在置换g之下保持不变的x的个数。计算gG|F(g)|显然比计算xX|Gx|容易，而且：g G|F(g)|=x X|Gx|利用下列矩阵计数：x g g行x列有表示：g(x)=x 按行算：每行数是在置换g之下不变的x的个数。总数即gG|F(g)|按列算：每列数是保持特定x不变的置换的个数，总数即xX|Gx|Burnside定理定理lxX|Gx|=t|G|lgG|F(g)|=xX|Gx|l於是：GggFGt)(|1 项链问题的解项链问题的解3个黑珍珠和个黑珍珠和6个白珍珠能做出多少样式不同的项链？个白珍珠能做出多少样式不同的项链？|X|=84,即C93(Why?)|G|=18 9个旋转，2个翻转对每个翻转g,|F(g)|=4旋转0的|F(g)|=84;旋转120 和240 的|F(g)|各各为3；其它均为0。结果是：(49+84+32)/18 =轴翻转顺 时 针 旋 转80F(g)表示在置换g之下保持不变的x的个数