组合数学讲义6章波利亚定理

上传人:飞*** 文档编号:26974383 上传时间:2018-01-04 格式:PDF 页数:60 大小:591.06KB
返回 下载 相关 举报
组合数学讲义6章波利亚定理_第1页
第1页 / 共60页
组合数学讲义6章波利亚定理_第2页
第2页 / 共60页
组合数学讲义6章波利亚定理_第3页
第3页 / 共60页
组合数学讲义6章波利亚定理_第4页
第4页 / 共60页
组合数学讲义6章波利亚定理_第5页
第5页 / 共60页
点击查看更多>>
资源描述

《组合数学讲义6章波利亚定理》由会员分享,可在线阅读,更多相关《组合数学讲义6章波利亚定理(60页珍藏版)》请在金锄头文库上搜索。

1、组合数学 第六章 波利亚定理1/60 第六章 P l y a ( 波 利 亚 ) 定 理6.1 群 论 基 础普通代数:计算对象为数,运算方式多为加、减、乘、除。扩展:计算对象为一般的集合元素,运算方式也可以是多种多样。例如矩阵运算、集合的并、交、差运算等。抽象代数:应用:代数、计数、通信编码、信息与网络安全等。 6.1.1 群 的 概 念定义 6.1.1 给定非空集合 G 及定义在 G 上的二元运算 “ ” ,若满足以下四个条件,则称集合 G 在运算“ ”下构成一个群,简称 G 为一个 群 。 :( 1)封闭性: a, b G,则 a b G;( 2)结合律: ( a b) c a (b c

2、);( 3)单位元:存在 e G,对任意 a G,有 a e e a a;( 4)逆元素:对任意 a G,存在 b G,使得 a b b a e,称 b 为 a 的逆元素,记为 a 。群的运算符“ ”可略去,即 a b ab . 群的运算并不要求满足交换律。如果某个群 G 中的代数运算满足交换律,则称 G 为 交换群 或 Abel 群 。群的元素可以是有限个,叫作 有限群 ;也可以是无限个,叫 无限群 。 以 |G|表示有限群中元素的个数,称为群的 阶 ,那么当 G 为无限群时,可以认为 |G|。例 6.1.1 偶数集,整数集 Z,有理数集 Q,实数集 R,复数集C 关于数的加法构成群,称为加

3、法群。因为数的运算对加法满足要求( 1)和( 2) 。其中的单位元为0,每个数 a 关于加法的逆元为: a a。组合数学 第六章 波利亚定理2/60 但是,关于数的乘法,这些集都不构成群。因为在偶数集中关于普通乘法不存在单位元。而在 Z、 Q、 R、 C 中,虽然关于普通乘法有单位元 1,但数 0 没有逆元。例 6.1.2 不含零的有理数集 Q1,实数集 R1 和复数集 C1 关于数的乘法构成群其中单位元为 e 1,数 a 的逆元为aa11 。例 6.1.3 G 1, 1关于乘法构成群单位元为 e 1, 由于 ( 1) 1 1, 所以数 a 1 的逆元为它自身。例 6.1.4 更一般情形,集合

4、 G1 e 1, G2 1, 1, G31,231 i ,231 i ) (1 的 3 次 根 ), , , Gn ak e i k2/n| k 0, 1, , , n 1, i 1 ( n 1, 2, , )均关于乘法构成 群 。 其 中 单 位 元 为 e 1 , 设 221 in eq nin2sin2cos ,则元素 ak qk 的逆元为 1ka q k qn k . 例 6.1.5 G 0, 1, , , n 1在模 n(即 mod n)的情况下关于加法运算构成群,当 n 为素数时, 1G 0G 1n21 , 关于乘法运算也构成群。在群 G 中,单位元为 0,元素 Ga 的逆元为 a

5、 或 n a。而在 1G 中,单位元则为 1, a 的逆元为 naa a mod11 。但对于某些特殊元素,其逆是显然的,如 11 1 , 11n 1 或 1n 。例 6.1.6 所有 m*n 矩阵关于矩阵加法,所有非奇异(即可逆)n 阶矩阵关于矩阵乘法都构成群。前者是可交换的,后者是不可交换群。例 6.1.7 二维欧几里德空间的刚性旋转变换集合 T T 构成阿贝尔群。其中 T 、 T 的二元运算 T *T 定义为:先做 T ,再对其结果做 T 。验证组合数学 第六章 波利亚定理3/60 T : 11yx cossin sincos yx( 1)封闭性: T *T T T ( 2)结合律:显然

6、,( 3)单位元: T0 对应矩阵为 E 10 01( 4)逆元素: ( T ) 1 T例 6.1.8 设 G f1 x, f2 1 x, f3 1/ x , f4 1 1/ x ,f5 1/ (1 x ) , f6 1 1/ (1 x ), 定义 G 上的二元运算, fi* fj fi( fj( x) ),则 G 构成群。( 证 )首先 G ,其次:( 1) 可以逐一验证 fi* fj fi( fj( x) ) G ;( 2) 同样可以逐一验证: fi* ( fj * fk) ( fi* fj) * fk;( 3) 单位元为 f1 x;( 4) f4 , f5 互为逆元,其他 fi 的逆元是

7、自身。 6.1.2 群 的 性 质定理 6.1.1 群具有以下性质( 1)单位元 e 唯一;( 2)逆元唯一;( 3)满足消去律:即对 a, b, c G,若 ab ac,则 b c;若 ba ca,则仍有 b c;( 4) a, b G,则 (ab) 1 b 1a 1,更一般有 (ab, c) 1 c 1,b 1a 1;( 5) 若 G 是有限群, 则对任意 a G, 必存在一个最小常数 r,使 ar e,从而 11 raa 。 r 称为元素 a 的阶。组合数学 第六章 波利亚定理4/60 ( 证 )性质( 1)( 4)显然。只证明性质( 5) 。设 |G| n,由 G 的定义知 . iia

8、aaa个 ai G, i 1, 2, , , n 1 由抽屉原理知,必存在整数 m, k,满足 1 mk n 1,使得 am ak,即 ak m e,令 r k m,则 ar e,即 a. ar 1 e,所以 a 1 ar 1. 6.1.3 子 群定义 6.1.2 设 G 是群, H 是 G 的子集, 若 H 在 G 的原有运算下也构成一个群,则称 H 是 G 的 子群 。例 6.1.9 任何群 G 至少有两个子群: H1 G, H 2 e| e G为单位元 。例 6.1.10 对于乘法运算, H 1, 1是 G 1, 1, i,i的子群。例 6.1.11 偶数加法群是整数群 Z 的子群, Z

9、 是有理数加法群 Q的子群, Q又是实数加法群 R的子群, R是复数加法群 C的子群;对乘法群而言,也有 Q1 是 R1 的子群, R1 是 C1 的子群。例 6.1.12 任选群 G 的一个元素 a,设 a 的阶为 r,则 H a,a2, , ar 1, ar e是 G 的子群。这样的群 H 是由某个固定元素a 的乘方组成,称为 循环群 ,或称 H 是由元素 a 生成的群, a 叫作 H 的 生成元 。例如, G 1,2,3,4,5,6关于模 7 的乘法构成循环群,其生成元为 3 3, 23 , 33 , 43 , 53 , 63 3, 2, 6, 4, 5, 1 另外,以 2 为生成元,可

10、以得到 G的一个子群H 2, 22 , 32 2,4,1 定理 6.1.2 有限群的阶数必能被其子群的阶数整除。组合数学 第六章 波利亚定理5/60 ( 证 ) (略) 。伽罗华 ( variste Galois, 1811 1832)简介:是法国对函数论、方程式论和数论作出重要贡献的数学家,他的工作为群论(一个他引进的名词)奠定了基础。源自他尚在校就读时欲证明五次多项式方程根数解 ( Solution by Radicals)的不可能性(其实当时已为阿贝尔( Abel)所证明,只不过伽罗华并不知道) , 和描述任意多项式方程可解性的一般条件的打算。于 1829 年将论文送交法兰西科学院时,

11、第一次所交论文却被柯西( Cauchy)遗失了,第二次则被傅立叶( Fourier)所遗失;他还与埃科尔综合技术学院( cole Polytechnique)的口试主考人发生顶撞而被拒绝给予一个职位。第三次送交科学院的论文亦为泊松( Poisson)所拒绝。伽罗华死于一次决斗, 可能是被保皇派或警探所激怒而致, 时年 21 岁。他被公认为数学界两个最具浪漫主义色彩的人物之一。评论: “数学史上最年轻、 最富有创造性的头脑停止了思考” 。“他的死使数学的发展被推迟了几十年,他就是伽罗华” 。6.2 置 换 群不论在理论研究还是在实际应用中,置换群都是十分重要的一类群。一方面,任何有限群都可以用它

12、表示;另一方面,在解决“代数方程是否能用根号求解”这个问题时,要用到它;它还在本章的 Burnside引理及 P lya 定理中起着基本作用。(一)置换定义 6.2.1 有限集合 S 到自身的一个映射叫做一个 置换 。组合数学 第六章 波利亚定理6/60 例如 S a1, a2, a3, a4, p13424321aaaaaaaa即是一个置换。相应的映射是?: a1 ?(a4), a2 ?(a1), a3 ?(a3), a4 ?(a2) . 或 ?(a1) a2, ?(a2) a4, ?(a3) a3, ?(a4) a1说明 :( 1) 将 S 中的元素 ai 写在上一行 (顺序可任意 ),

13、ai 的象写在ai 之下,同一列的两个元素的相对关系只要保持不变,即 ?(ai)ika ,不同形式的写法都认为是同一个置换。如321321aaa213213aaa( 2)置换就是将 n 个元的一种排列变为另一种排列。( 3) n 元集 S 共有个 n!不同的置换。(二)置换的运算定义 6.2.2 两个置换 p1、 p2 的乘积 p1p2 定义为先做置换 p1 再做 p2 的结果。例如 p1 4213 4321 , p2 1234 4321 , 那么p1p24213432112344321 13424321即 1 1p 3 2p 2 ,2 1p 1 2p4,,一般来说,置换的乘法不满足交换律,即

14、 p1p2 p2p1,如上例中组合数学 第六章 波利亚定理7/60 p2p1 1234432142134321 31244321 p1p2求复合置换的一种 技巧 就是更改 p2 各列的前后次序,使其第一行的排列与前者 p1 第二行的排列相同, 那么复合置换 p1 p2 的第一行就是 p1 的第一行,其第二行是 p2 的第二行。如上例p1p24213432112344321 421343211342421313424321定理 6.2.1 设 Sn 是 n 元集合上的所有置换构成的集合,则Sn 关于置换的乘法构成 群,称为 n 次 对称群 。( 证 ) 由置换乘法的定义知,封闭性,结合律显然成立

15、。其次,单位元为恒等置换e nn.21.21逆元素121 .21naaannaaa n.21.21例如1p 1314243214321314224134321(三)置换与空间刚体变换从几何变换角度看问题, 由于几何图形的对称性与数字序列的组合数学 第六章 波利亚定理8/60 置换之间存在着一一对应关系,从而形成一种同构。因此,置换群的运算和理论就成了对称图形运算和计数的基本工具。例 6.2.1 将顶点分别为 1, 2, 3 的正三角形(见图 6.2.1 )绕重心 O沿逆时针方向分别旋转 00、 1200、 2400,视其为顶点集 1 ,2, 3 的置换,则有旋转对称映射oep01231231转,op1 2 02 3 11 2 32转,op2403121233转另一类是反射对称映射,即将三角形 123 分别绕对称轴 1A、2B、 3C 反转 1800得顶点集的另一类置换:p4 213123(绕 3C), p5 321123(绕 2B), p6 132123(绕 1A)1 B C 3 2 A 图 6.2.1 3S 与正三角形的对应示意图因此描述正三角形的全部对称的映射,

展开阅读全文
相关资源
相关搜索

当前位置:首页 > 研究报告 > 综合/其它

电脑版 |金锄头文库版权所有
经营许可证:蜀ICP备13022795号 | 川公网安备 51140202000112号