置换群在计数中的应用.ppt

单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,*,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,单击此处编辑母版标题样式,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,PART,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,*,单击此处编辑母版标题样式,单击此处编辑母版文本样式,第二级,第三级,第四级,第五级,*,置换群在计数中的应用,净听我瞎扯淡吧【笑,1,1,你要知道置换群是什么鬼,2,一,置换群,的基本概念,定义1,任一集合,A,到自身的映射都叫做的,A,一个,变换，如果,A,是有限集且变换是一一变换（双射），,那么这个变换为,A,的一个置换。有限集合,A,的若干,个置换若作成群，就叫做置换群。含有,n,个元素的,有限群,A,的全体置换作成的群，叫做,n,次对称群。,通常记为,Sn,。,3,置换群,是一种特殊的变换群。换句话说，置换群就是有限集上的,变换群,。由于是定义在有限集上，故每个置换的表现形式，固有特点都是可揣测的。,大家应该知道什么是变换群吧？,封闭性、可结合、有单位元、存在逆元,4,5,6,举个栗子,7,p119,8,9,关于循环置换,10,2,这个置换群在计数中到底有什么应用,11,等价类计数,12,瞅一道题吧,用,6,种不同颜色给正方体的六个面着色，每个面有,6,中选择，假如给定每个面的编号，不同的着色序列有,6,！,(=720),个，但哪些是“,真正,”不同的？,因此：不同的着色有,6!/(6+3+6+8+1)=30,种,90,18,0,18,0,12,0,6,种,3,种,6,种,8,种,1,种,13,其实我并没有看太明白,14,接下来我就要介绍一种简单粗暴的方法,15,如果不是每个面的着色都不同,比如有两个面是红的，如何判断两种着色是“,真正,”不同？,设着色对象的集合是,S,，允许使用的颜色的集合是,C,(,我们只考虑有限集,),。一种着色方案就是一个函数,f,:,S,C,。,f,与,f,2,被认为“,实际上,”是一样的，当且仅当在所允许的变换,(,即前面例子中的对称旋转,),下，,f,1,能转变为,f,2,或相反。,而对称旋转即置换群的元素。我们称“,(,置换,),群作用于,S,，也作用于,C,。”,其实我们看一下群与对称更好额,16,比立方体简单一点的例子,3,个黑珍珠和,6,个白珍珠能做出多少样式不同的项链？,轴,翻转,顺时针旋转,80,17,置换群诱导的等价关系,假设,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,的,轨道,。,18,保持,x,不变的置换构成子群,G,中所有,“将,x,变为,y”,的置换,构成的集合：,G(x,y),=,g,|,g,G,且,g,(x)=y,G,中所有,“保持,x,不变”的置换,的集合：,G,x,=,g,|,g,G,且,g,(x)=x,注意：,G,x,构成子群,(,只需证明封闭性,),。,G(x,y),是,G,x,的右陪集：,h,G(x,y),G(x,y)=G,x,h,若,G,x,h,令,=,h,(,G,x,),则,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,G,x,G,x,h,19,轨道的大小,子群与相应的陪集等势，因此：若,y,Gx,|G(x,y)|=|G,x,|,否则,|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)|=|G,x,|,个,，否则为空列。所以：,|Gx|,|G,x,|=|G|,20,y,Gx,|G,y,|,值与所在轨道无关,对任意的,y,X,若,y,Gx,则,|G,x,|=|G,y,|,实际上，,G(x,y),是,G,y,的左陪集：即,h,G(x,y),G(x,y)=,h,G,y,若,h,G,y,令,=,h,(,G,y,),则,x,X,(x)=,(,h,(x)=,(y)=y,G(x,y),若,G(x,y),则,y,X,(,h,-1,(y)=,(x)=y,即,h,-1,G,y,h,G,y,所以，对每个轨道，,y,Gx,|G,y,|=|Gx|,|G,x,|=|G|,y,Gx,|G,y,|,是“,一个轨道中保持各元素不变的置换的总数,”,21,轨道的个数,令轨道数为,t,因为每个轨道中保持各元素不变的置换的总数均为,|G|,x,X,|G,x,|=,t,|G|,。,F,(,g,),表示在置换,g,之下保持不变的,x,的个数。计算,g,G,|,F,(g)|,显然比计算,x,X,|G,x,|,容易，而且：,g,G,|F(g)|=,x,X,|G,x,|,利用下列矩阵计数：,x,g,g,行,x,列有,表示：,g,(x)=x,按行算：每行,数是在置换,g,之下不变的,x,的个数。总数即,g,G,|F(g)|,按列算：每列,数是保持特定,x,不变的置换的个数，总数即,x,X,|G,x,|,22,Burnside,定理,x,X,|G,x,|=t|G|,g,G,|F(g)|=,x,X,|G,x,|,於是：,23,24,25,项链问题的解,3,个黑珍珠和,6,个白珍珠能做出多少样式不同的项链？,|X|=84,即,C,9,3,(,Why?,),|G|=18 9,个旋转，,2,个翻转,对每个翻转,g,|F(g)|=4,旋转,0,的,|F(g)|=84;,旋转,120,和,240,的,|F(g)|,各,为,3,；,其它均为,0,。,结果是：,(49+84+32)/18,=,轴,翻转,顺时针旋转,80,F,(,g,),表示在置换,g,之下保持不变的,x,的个数,26,27,28,终于讲完了，谢谢大家,有没有,get,到一点东西呢,最后推荐对群感兴趣的同学可以去,图书馆看一看近世代数或者抽象代数,29,