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

置换群在计数中的应用1你要知道置换群是什么鬼一．置换群的基本概念定义1任一集合A到自身的映射都叫做的A一个变换，如果A是有限集且变换是一一变换（双射），那么这个变换为A的一个置换。有限集合A的若干个置换若作成群，就叫做置换群。含有n个元素的有限群A的全体置换作成的群，叫做n次对称群。通常记为Sn。置换群是一种特殊的变换群。换句话说，置换群就是有限集上的变换群。由于是定义在有限集上，故每个置换的表现形式，固有特点都是可揣测的。大家应该知道什么是变换群吧？封闭性、可结合、有单位元、存在逆元举个栗子g√g行x列有√表示：g(x)=x传递性：由群的封闭性保证。将关系""所决定的等价类记为Gx:而对称旋转即置换群的元素。|X|=84,即C93(Why?)G(xy)={g|gG,且g(x)=y}x定义X上的关系“”如下：我们称“(置换)群作用于S，也作用于C。其实我们看一下群与对称更好额给定xX,构造如下的矩阵：定义1任一集合A到自身的映射都叫做的A一个而对称旋转即置换群的元素。因此：不同的着色有6!/(6+3+6+8+1)=30种x,yX,xygG,使得g(x)=y对每个翻转g,|F(g)|=4p119关于循环置换2这个置换群在计数中到底有什么应用等价类计数瞅一道题吧用6种不同颜色给正方体的六个面着色，每个面有6中选择，假如给定每个面的编号，不同的着色序列有6！(=720)个，但哪些是“真正”不同的？因此：不同的着色有6!/(6+3+6+8+1)=30种901801801206种3种6种8种1种其实我并没有看太明白接下来我就要介绍一种简单粗暴的方法如果不是每个面的着色都不同,比如有两个面是红的，如何判断两种着色是“真正”不同？设着色对象的集合是S，允许使用的颜色的集合是C(我们只考虑有限集)。一种着色方案就是一个函数f:SC。f与f2被认为“实际上”是一样的，当且仅当在所允许的变换(即前面例子中的对称旋转)下，f1能转变为f2或相反。而对称旋转即置换群的元素。我们称“(置换)群作用于S，也作用于C。”其实我们看一下群与对称更好额比立方体简单一点的例子3个黑珍珠和6个白珍珠能做出多少样式不同的项链？轴翻转顺时针旋转80置换群诱导的等价关系假设G是集合X上的置换群。定义X上的关系“”如下：x,yX,xy

gG,使得g(x)=y

“”是等价关系自反性：置换群中的单位元素一定是恒等映射。对称性：由群的逆元素性保证。传递性：由群的封闭性保证。将关系""所决定的等价类记为Gx:

Gx={y|yX,且gG,使得g(x)=y}这样的等价类称为X上G的轨道。保持x不变的置换构成子群G中所有“将x变为y”的置换构成的集合：

G(xy)={g|gG,且g(x)=y}G中所有“保持x不变”的置换的集合：

Gx={g|gG,且g(x)=x}注意：Gx构成子群(只需证明封闭性)。G(xy)是Gx的右陪集：hG(xy),G(xy)=Gxh若Gxh,令=h(Gx),

则xX,(x)=h((x))=h(x)=y,G(xy)若G(xy),

则xX,h-1((x))=h-1(y)=x,即h-1Gx,Gxh

轨道的大小子群与相应的陪集等势，因此：若yGx,|G(xy)|=|Gx|,否则|G(xy)|=0。对任意xX,x所在的轨道的大小与保持x不变的置换的个数的乘积与x无关。给定xX,构造如下的矩阵：

y

g√g行y列有√表示：g(x)=y对√计数：按行数：每行恰有1个√。总数为|G|。按列数，若某个yGx,则该列恰有|G(xy)|=|Gx|个√，否则为空列。所以：

|Gx||Gx|=|G|

yGx|Gy|值与所在轨道无关对任意的yX,若yGx,则|Gx|=|Gy|实际上，G(xy)是Gy的左陪集：即hG(xy),G(xy)=hGy若hGy,令=h(Gy),则xX,(x)=(h(x))=(y)=y,G(xy)若G(xy),则yX,(h-1(y))=(x)=y,即h-1Gy,

hGy所以，对每个轨道，yGx|Gy|=|Gx||Gx|=|G|,

yGx|Gy|是“一个轨道中保持各元素不变的置换的总数”轨道的个数

令轨道数为t,因为每个轨道中保持各元素不变的置换的总数均为|G|,xX|Gx|=t•|G|。F(g)表示在置换g之下保持不变的x的个数。计算gG|F(g)|显然比计算xX|Gx|容易，而且：

gG|F(g)|=xX|Gx|利用下列矩阵计数：

x

g√g行x列有√表示：g(x)=x

按行算：每行√数是在置换g之下不变的x的个数。总数即gG|F(g)|按列算：每列√数是保持特定x不变的置换的个数，总数即xX|Gx|Burnside定理xX|Gx|=t•|G|gG|F(g)|=xX|Gx|於是：

项链问题的解3个黑珍珠和6个白珍珠能做出多少样式不同的项链？|X|=84,即C93(Why?) |G|=189个旋转，2个翻转