复旦大学：《离散数学 Discrete Mathematics（下）》英文课件（赵一鸣）03/32

§2变换群、置换群与循环群 例148:证明不等边长方形所有对称的集 合,关于其合成·构成群。 B={e-B,y},B4;·是4元素群称为Kein 四元群

§2 变换群、置换群与循环群 • 例14.8:证明不等边长方形所有对称的集 合, 关于其合成•构成群。 • B4={e,,,},[B4 ;•]是4元素群,称为Klein 四元群

、变换群 变换非空集合S到S的一个映射, 当映射是一一对应时称为一一变换。 S表示S到S的所有映射全体组成的集合, SS={f:S→>S} ·SS;·是半群。是拟群。不是群 T(S表示S上所有一一变换组成的集合。 T(S=feS,且/为一—对应 IT(S);·是群

一、变换群 • 变换:非空集合S到S的一个映射, • 当映射是一一对应时, 称为一一变换。 • S S表示S到S的所有映射全体组成的集合, • S S={f|f:S→S}， • [S S ;•]是半群。是拟群。不是群 • T(S)表示S上所有一一变换组成的集合。 • T(S)={f|fS S ,且f为一一对应} • [T(S);•]是群

定义145:设G∈T(S,当[G;为群时就称 该群为变换彦其中●为一—变换的合成 (复合运算并称为变换的乘法。 定理149:[T(S);·是一个变换群。 变换群不一定是交换群

• 定义14.5:设GT(S),当[G;•]为群时,就称 该群为变换群,其中•为一一变换的合成 (复合)运算,并称为变换的乘法。 • 定理14.9:[T(S);•]是一个变换群。 • 变换群不一定是交换群

二、置换群 定义146:设S≠,SK+,S上的一个 变换称为置换。S上的某些置换关于乘法 运算构成群时,就称为置换群。 若|S=n,设S={1,2,,mn},其置换全体组成 的集合表示为Sn; Sn;是一个置换群,次对称碰

二、置换群 • 定义14.6:设S,|S|<+,S上的一个一一 变换称为置换。S上的某些置换关于乘法 运算构成群时, 就称为置换群。 • 若|S|=n,设S={1,2,,n},其置换全体组成 的集合表示为Sn ; • [Sn ;•]是一个置换群, n次对称群

S上的置换σ∈Sn,习惯上写成 12 (1)a(2)…o(n) 这里o()即为连在函数G下的象,这里1,2, ,n次序无关,即 d(1)a(2)…σ(n)(o(i1)a(i2)…σ(

        = (1) (2) ( ) 1 2 n n       • S上的置换Sn ,习惯上写成         =        = (1) (2) ( ) ( ) ( ) ( ) 1 2 1 2 1 2 n n i i i i i i n n            这里(i)即为i在函数下的象，这里1,2, ,n次序无关，即

2 恒等量换e 111 σ(1)a(2)…a(n) σ的邀置换 但习惯上重新躉理换士n重排,即 2 (1)a-1(2)

        =         =         = − − − − − σ (1) σ (2) σ (n) 1 2 n σ 但习惯上重新整理按1— n重排，即 1 2 n σ(1) σ(2) σ(n) σ的逆置换σ 1 2 n 1 2 n 恒等置换e 1 1 1 1 1      

n次对称群S是有限群问|Sn=? S上的一一变换个数有多少? S上的一一变换个数是n!,即Sn|=n! 下面以三次对称群S3为例, 考察群运算

• n次对称群Sn是有限群,问|Sn |=? • S上的一一变换个数有多少? • S上的一一变换个数是n!,即|Sn |=n!。 • 下面以三次对称群S3为例， • 考察群运算

12 般地对于σ= σ(1)a(2)…a(n) 12 有 τ(1)τ(2) 12 n 12 0●t 0(1)0(2)…o(mn)丿(τ(1)τ(2)…τ(m) τ(1)t(2) T(n o((1)0((2)…o(r(m))(τ(1)τ(2)…τ(m 2 0(τ(1)0(τ(2)…(tτ(m)

,有 τ(1)τ(2) τ(n) 1 2 n τ , σ(1)σ(2) σ(n) 1 2 n 一般地,对于σ         =         =             =         •         =         •         • = ( (1)) ( (2)) ( (n)) 1 2 n (1) (2) (n) 1 2 n ( (1)) ( (2)) ( (n)) (1) (2) (n) (1) (2) (n) 1 2 n (1) (2) (n) 1 2 n σ τ σ τ σ τ σ τ σ τ σ τ τ τ τ τ τ σ σ σ τ τ τ σ τ           τ

定义147:设|S=n,o∈Sn,形如: dd+ d+1 其中2<d≤n。这种形式的置换叫做循环置换 ,称其循环长度为d。上述o可写为o=(i1 a,其中在变换o下的象是自身的元素就不 再写出 特别,当d=2时称为对换

        = + − + d d n d d d n i i i i i i i i i i i i     2 3 1 1 1 2 1 1  • 定义14.7:设|S|=n, Sn , 形如: 其中2≤d≤n。这种形式的置换叫做循环置换 , 称其循环长度为d。上述可写为=(i1 ,…, id )，其中在变换下的象是自身的元素就不 再写出。 • 特别, 当 d=2时称为对换

定理14.10S中的任一个置换均可分解为 不含公共元的若干个循环置换的乘积。 证明对n作归纳 n=1,成立 假设对m>1,|S≤n-1,结论成立 当S=n,任取S中的置换σ 由元素出发取σ上的循环置换 推论14.1:任意一个置换可以分解为若干 个对换的乘积

• 定理14.10:Sn中的任一个置换均可分解为 不含公共元的若干个循环置换的乘积。 • 证明:对n作归纳 n=1,成立 假设对n>1，|S|n-1,结论成立 当|S|=n,任取Sn中的置换 由元素1出发取上的循环置换 • 推论14.1:任意一个置换可以分解为若干 个对换的乘积