#2624. [JSOI2007] 群的计数
[JSOI2007] 群的计数
题目描述
代数学研究的基本对象之一群是一些元素的集合。这些元素之间有一种代数运算,称之为乘法。两个群元素的乘积是一个群元素。一个大家习以为常的群是有理数乘法群,例如,等等,都是这个群中乘法的例子。需要注意的是,如果仅仅考虑有理数的乘法群,另外的一些运算比如加法是不被讨论的。数学家们把乘法抽象出来,就成为了群。群需要满足以下三条性质: 结合律:对群中的任意元素a,b,c 有 a(bc)=(ab)c 单位元:在群中存在唯一的元素e,它对群中任意的元素a有ea=a,ae=a 有理数乘法群的单位元是1 逆 元:对群中任意元素a,都存在群中唯一的元素b,使得ab=ba=e 比如有理数乘法群中,23的逆元就为。从这里可以看出,整数乘法不能构成一个群 需要注意的是,群的定义中并没有交换律,就是说ab不一定等于ba,有理数乘法群作为一个特例,其交换性是没有普遍的意义的 现在的问题是,给定群的元素的个数(群的阶数),需要知道这样的群有多少种。只要满足上述三条性质,就是群,应该算上。 下面用四阶群的例子来说明这个问题。抽象地记群元素为e,a,b,c 只要列出一个乘法表,就可以代表一个群。下面给出推导乘法表的步骤: 群1|e|a|b|c| :-:|:-:|:-:|:-:|:-:| ee (1)a (1)b (1)c (1) aa (1)e (2)c (3)b (3) bb (1)c (3)e (4)a (5) cc (1)b (3)a (5)e (5) 群1eabc ee (1)a (1)b (1)c (1) aa (1)e (2)c (3)b (3) bb (1)c (3)e (4)a (5) cc (1)b (3)a (5)e (5) 有单位元素的性质,可以填上 aa可能为e,b,c,但不可能为a,否则aa=a两边乘以a的逆元,得到a=e; aa=b和aa=c的情况是一样的,只是乘法表中元素的位置进行了一个变换,本质没有改变,称为一个群同构;此时可以把aa得到的元素称为b; 所以只要讨论aa=e和aa=b的情况;下面先讨论aa=e的情况 ab不能为a或e,ab为b的话,a=e,也矛盾,所以ab=c;同理可填上所有的(3) bb=e时,bc=cb=a,cc=e,得到群1 bb=a时,bc=cb=e,cc=a,得到群2 群2|e|a|b|c| :-:|:-:|:-:|:-:|:-:| ee (1)a (1)b (1)c (1) aa (1)e (2)c (3)b (3) bb (1)c (3)a (4)e (5) cc (1)b (3)e (5)a (5) 群2eabc ee (1)a (1)b (1)c (1) aa (1)e (2)c (3)b (3) bb (1)c (3)a (4)e (5) cc (1)b (3)e (5)a (5) 当aa=b时,按照标号顺序可填出下列的群: 群 2’|e|a|b|c| :-:|:-:|:-:|:-:|:-:| ee (1)a (1)b (1)c (1) aa (1)b (2)c (4)e (3) bb (1)c (4)e (6)a (5) cc (1)e (3)a (5)b (6) 群 2’eabc ee (1)a (1)b (1)c (1) aa (1)b (2)c (4)e (3) bb (1)c (4)e (6)a (5) cc (1)e (3)a (5)b (6) 但需要注意的是,这并没有得到一个新的群,把群2中的a,b调换位置,就得到了群2’。群2’只是群2的一个同构而已。 综上所述,四阶群一共有2种。 虽然4阶群一定有交换律,但这里再次提醒,这并非一个普遍现象。
输入格式
输入群的阶数n(4<=n<=3000)。
输出格式
输出n阶群的种类数。
4
2
提示
Hint 注意并灵活运用群的三条性质
题目来源
没有写明来源