以文本方式查看主题

-  中文XML论坛 - 专业的XML技术讨论区  (http://bbs.xml.org.cn/index.asp)
--  『 计算机考研交流 』   (http://bbs.xml.org.cn/list.asp?boardid=67)
----  一道关于群的题的疑惑  (http://bbs.xml.org.cn/dispbbs.asp?boardid=67&rootid=&id=68862)


--  作者:kaogejj
--  发布时间:10/29/2008 11:24:00 PM

--  一道关于群的题的疑惑

此主题相关图片如下:
按此在新窗口浏览图片
第一问我不解
根据书上定理17.19的(1)的结论,任何p阶轮换(当然也是p元置换,也属于Sp)的阶都是p,那么Sp的p阶元应该是p!,题中怎么说是(p-1)! 呢?
--  作者:kaogejj
--  发布时间:10/30/2008 8:23:00 PM

--  
有人知道吗谢谢?
--  作者:Logician
--  发布时间:10/30/2008 9:21:00 PM

--  
(1 2 3 4) = (2 3 4 1) = (3 4 1 2) = (4 1 2 3)
并不是p的每个不同的排列都对应一个不同的p-轮换,相反,每p个排列对应一个p-轮换
所以总共有p!/p = (p-1)!个p-轮换
--  作者:kaogejj
--  发布时间:10/30/2008 10:51:00 PM

--  
以下是引用Logician在2008-10-30 21:21:00的发言:
(1 2 3 4) = (2 3 4 1) = (3 4 1 2) = (4 1 2 3)
并不是p的每个不同的排列都对应一个不同的p-轮换,相反,每p个排列对应一个p-轮换
所以总共有p!/p = (p-1)!个p-轮换

解释地非常清楚,谢谢。群这样一章特别是置换群这一张我感觉有点难,看地很慢,以函数为元素的集合考虑起来有点费神。。。


--  作者:kaogejj
--  发布时间:10/30/2008 11:06:00 PM

--  
以下是引用Logician在2008-10-30 21:21:00的发言:
(1 2 3 4) = (2 3 4 1) = (3 4 1 2) = (4 1 2 3)
并不是p的每个不同的排列都对应一个不同的p-轮换,相反,每p个排列对应一个p-轮换
所以总共有p!/p = (p-1)!个p-轮换

只是有点疑问,每p个排列对应一个p-轮换,书上没有这个结论。但我觉得它是对的,可是我又想不出如何证明它?能否给点提示?


--  作者:Logician
--  发布时间:10/30/2008 11:21:00 PM

--  
以下是引用kaogejj在2008-10-30 23:06:00的发言:
[quote]以下是引用Logician在2008-10-30 21:21:00的发言:
(1 2 3 4) = (2 3 4 1) = (3 4 1 2) = (4 1 2 3)
  并不是p的每个不同的排列都对应一个不同的p-轮换,相反,每p个排列对应一个p-轮换
  所以总共有p!/p = (p-1)!个p-轮换
[/quote]

只是有点疑问,每p个排列对应一个p-轮换,书上没有这个结论。但我觉得它是对的,可是我又想不出如何证明它?能否给点提示?


大致这样想吧:
1、如果一个p-轮换f = (i_1 i_2 i_3 ... i_p),不妨设其中i_k=1,那么我们可以把f重写成(i_k i_{k+1} i_{k+2} ... i_p i_1 i_2 ... i_{k-1})。显然,这个写法和原来的f是等价的。
2、上面这个论证是说,对每一个p-轮换f,至少存在一个“以1开头的p的全排列”与之对应。反过来,你可以证明,这种与之对应的“以1开头的p的全排列”是唯一的。这样p-轮换的个数就和“以1开头的p的全排列”的个数相同。而后者的数量是(p-1)!(因为它是“从2到p”这p-1个数字的所有全排列)。



--  作者:kaogejj
--  发布时间:10/31/2008 7:42:00 AM

--  
以下是引用Logician在2008-10-30 23:21:00的发言:
[quote]以下是引用kaogejj在2008-10-30 23:06:00的发言:
[quote]以下是引用Logician在2008-10-30 21:21:00的发言:
  (1 2 3 4) = (2 3 4 1) = (3 4 1 2) = (4 1 2 3)
   并不是p的每个不同的排列都对应一个不同的p-轮换,相反,每p个排列对应一个p-轮换
   所以总共有p!/p = (p-1)!个p-轮换
  [/quote]

  只是有点疑问,每p个排列对应一个p-轮换,书上没有这个结论。但我觉得它是对的,可是我又想不出如何证明它?能否给点提示?
[/quote]

大致这样想吧:
1、如果一个p-轮换f = (i_1 i_2 i_3 ... i_p),不妨设其中i_k=1,那么我们可以把f重写成(i_k i_{k+1} i_{k+2} ... i_p i_1 i_2 ... i_{k-1})。显然,这个写法和原来的f是等价的。
2、上面这个论证是说,对每一个p-轮换f,至少存在一个“以1开头的p的全排列”与之对应。反过来,你可以证明,这种与之对应的“以1开头的p的全排列”是唯一的。这样p-轮换的个数就和“以1开头的p的全排列”的个数相同。而后者的数量是(p-1)!(因为它是“从2到p”这p-1个数字的所有全排列)。




对,谢谢。


--  作者:cuiwenhuan
--  发布时间:11/17/2008 10:06:00 PM

--  
p阶轮换就是(p-1)!个嘛!因为可以看成一个环,固定任何一个,其它n-1个元素全排列。
而(1)成立也就意味着p阶轮换和Sp的p阶元是一一对应的
--  作者:cuiwenhuan
--  发布时间:11/17/2008 10:12:00 PM

--  
至于怎么证明任何p阶元都可以表示成p阶轮换,我觉得可以从任意n元置换都可以表成不相交的轮换之积去考虑。great Logician,你觉得呢?
--  作者:whasic
--  发布时间:11/17/2008 10:35:00 PM

--  
谈一下我的看法
首先我觉得楼上同学的表述有很大的问题
想当然的成分太大
而且“环”这个ms不在置换群的定义体系里吧

设d是Sp的一个元素
现证|d|=p,则d可以写成(ik1,ik2,。。。。ikl)的形式
假设d不能写成上述形式,则d写成d=t1t2...tm的乘积的形式
其中t1 t2 。。。tm是不交的轮换 并且t1 t2 。。。tm的阶为a1 a2 。。。am
并且它们都显然是小于p的
则由定理17.19之二 p=|d|=[a1,a2....,am]
与p是素数矛盾
再证l=p
假设l和p不相等
则由定理17.19之一 |d|=l 与|d|=p矛盾
因此 d可以写成(ik1,ik2,。。。。ikp)的形式
再证这样的排列有(p-1)!个
任取d中的一个元素比如a
则d(a)必然不等于a
否则d可以写成d=(a)t的形式 与已证矛盾
不妨令d(a)=b
则d(b)不等于b且d(b)不等于a 那么 d(a)有p-1个可取的值
不等于b是因为一一映射 不等于a是因为若等于a 则d可以写成d=(ab)t的形式
与已证矛盾 故d(b)有p-2个可取的值
一直推下去 到第p-1个元素 只有一个可取的值
对于第p个元素,设为x 则d(x)别无选择,只能为a
故共有(p-1)*(-2)......2*1*1=(p-1)!个p阶元


--  作者:cuiwenhuan
--  发布时间:11/18/2008 6:34:00 PM

--  
呃我的“环”的意思是个圈,类似与数据结构里的循环队列,是说怎么旋转都是一个轮换。。。
我根本没想把详细过程写下来,因为太麻烦了。楼上写的基本思路和我一样。不过写出来了很有耐心啊。我觉得最重要的是交流关键思路,而不是完整过程。一点就通最好。
--  作者:whasic
--  发布时间:11/18/2008 11:31:00 PM

--  
……
--  作者:深白色的阳光
--  发布时间:12/19/2008 2:54:00 PM

--  
10楼解答的很详细哈,ms每一步都是反证法......

我认为,在这一步上:(红色字体为引用10楼内容,下同)

再证这样的排列有(p-1)!个
……
……
故共有(p-1)*(-2)......2*1*1=(p-1)!个p阶元

我们可以使用组合数学中的递推公式来解决:在有了这一步为前提下

任取d中的一个元素比如a
则d(a)必然不等于a
否则d可以写成d=(a)t的形式 与已证矛盾

问题转化为,从1到p,共p个数排列,要求p不能排列在第p个位置上,共多少种排法?
设p=n时有H(n)种排法:
显然有H(2)=1。 (*)

又因为当有n-1个数已经在1到n-1的位置上错位排列好后,数n不能排列在第n个位置上,所以对前面的H(n-1)中排法的每一种,n都可以排列在1到n-1的任何一个位置上,而原处在该位置的数可排在第n个位置上,故有H(n)=(n-1)*H(n-1)  (**)

由(*)式和(**)式可得,H(n)=(n-1)!
所以,Sp恰有(p-1)!个p阶元。

PS:不知这么答题的话,考试的时候能不能答完……


W 3 C h i n a ( since 2003 ) 旗 下 站 点
苏ICP备05006046号《全国人大常委会关于维护互联网安全的决定》《计算机信息网络国际联网安全保护管理办法》
6,132.813ms