16-置换群的应用.ppt

《16-置换群的应用.ppt》由会员上传分享，免费在线阅读，更多相关内容在教育资源-天天文库。

1、置换群的应用离散数学第16讲上一讲内容的回顾变换和变换群置换及其表示置换群任意群与变换群同构置换群的应用置换群的应用置换群诱导的等价关系轨道轨道的大小轨道的个数-Burnside定理Burnside定理的应用相同？不同？xyztf(x,y,z,t)4个变量,可能的输入值有24个;因此,可以定义216(65,536)个不同的函数。但是，真的需要这么多种电路吗？xyx⋁yztz⋁tf(x,y,z,t)由于对称性，只要调整接入线，同样的电路可以实现不同的函数。等价类计数如果定义上述函数的集合上的关系R：函数f1,f2满足关系关系R当且仅当它们可以用同一个电

2、路实现(只需调整接入方式，也可以用外部转相器)。显然，上述关系R是等价关系。可以用同一电路实现的所有函数包含在同一个等价类中。因此，计算需要多少种不同电路才能实现所有可能的函数问题就转化为等价类计数问题。对称在计数中的作用用6种不同颜色给正方体的六个面着色，每个面有6中选择，假如给定每个面的编号，不同的着色序列有6！(=720)个，但哪些是“真正”不同的？901801801206种3种6种8种1种因此：不同的着色有6!/(6+3+6+8+1)=30种更一般的情况如果不是每个面的着色都不同,比如有两个面是红的，如何判断两种着色是“真正”不同？

3、设着色对象的集合是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“”是等价关系自反性：置换群中的单位元素一定是恒等映射。

4、对称性：由群的逆元素性保证。传递性：由群的封闭性保证。将关系""所决定的等价类记为Gx:Gx={y

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

6、gG,且g(x)=y}G中所有“保持x不变”的置换的集合：Gx={g

7、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(

8、xy)若G(xy),则xX,h-1((x))=h-1(y)=x,即h-1Gx,Gxh轨道的大小子群与相应的陪集等势，因此：若yGx,

9、G(xy)

10、=

11、Gx

12、,否则

13、G(xy)

14、=0。对任意xX,x所在的轨道的大小与保持x不变的置换的个数的乘积与x无关。给定xX,构造如下的矩阵：yg√g行y列有√表示：g(x)=y对√计数：按行数：每行恰有1个√。总数为

15、G

16、。按列数，若某个yGx,则该列恰有

17、G(xy)

18、=

19、Gx

20、个√，否则为空列。所以：

21、Gx

22、

23、Gx

24、=

25、G

26、yGx

27、Gy

28、值与所在轨道无关对任意的

29、yX,若yGx,则

30、Gx

31、=

32、Gy

33、实际上，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

34、Gy

35、=

36、Gx

37、

38、Gx

39、=

40、G

41、,yGx

42、Gy

43、是“一个轨道中保持各元素不变的置换的总数”轨道的个数令轨道数为t,因为每个轨道中保持各元素不变的置换的总数均为

44、G

45、,xX

46、Gx

47、=t•

48、G

49、。

50、F(g)表示在置换g之下保持不变的x的个数。计算gG

51、F(g)

52、显然比计算xX

53、Gx

54、容易，而且：gG

55、F(g)

56、=xX

57、Gx

58、利用下列矩阵计数：xg√g行x列有√表示：g(x)=x按行算：每行√数是在置换g之下不变的x的个数。总数即gG

59、F(g)

60、按列算：每列√数是保持特定x不变的置换的个数，总数即xX

61、Gx

62、Burnside定理xX

63、Gx

64、=t•

65、G

66、gG

67、F(g)

68、=xX

69、Gx

70、於是：项链问题的解3个黑珍珠和6个白珍珠能做出多少样式不同的项链？

71、X

72、=84,即C93(Why?)

73、G

74、=189个旋转，9

75、个翻转对每个翻转g,

76、F(g)

77、=4旋转0°的

78、F(g)

79、=84;旋转120°和240°的

80、F(g)

81、各为3