第四章Plya定理 群的概念 置换群 循环、奇循环与偶循环 Burnside引理 Polya定理 例 母函数型的 Polya定理 图的计数
第四章 Pólya定理 • 群的概念 • 置换群 • 循环、奇循环与偶循环 • Burnside引理 • Pólya定理 • 例 • 母函数型的Pólya定理 • 图的计数
41群的概念 (1)群 定义给定集合G和G上的二元运算·,满足 下列条件称为群 (a)封闭性:若ab∈G,则存在c∈G使得ab=c (b)结合律成立:任意ab,c∈G有(ab)c=abc (c)有单位元:存在eeG任意a∈G a·e=e°a=a. (d有逆元:任意a∈G存在b∈G,ab=ba=e.b=a 由于结合律成立,(ab)c=a(bc)可记做abc 例证明对于a1,a2a.乘积,结合律成立 aa…"a=a(共n个a相乘)
4.1 群的概念 (1)群 定义 给定集合G和G上的二元运算 · ，满足 下列条件称为群。 (a)封闭性：若a,b∈G,则存在c∈G,使得a·b=c. (b)结合律成立：任意a,b,c∈G,有(a·b)·c=a·(b·c). (c)有单位元：存在e∈G,任意a∈G.a·e=e·a=a. (d)有逆元：任意a∈G,存在b∈G, a·b=b·a=e. b=a. 由于结合律成立，(a·b)·c=a·(b·c)可记做a·b·c. 例 证明对于a1,a2,…,an的乘积，结合律成立. a·a·…·a=a (共n个a相乘). -1 n
4.1群的概念 (2)简单例子 例G={11}在普通乘法下是群。 例G={0,12,…,n-1}在modn的加法下是群 例二维欧氏空间所有刚体旋转T={Ta}构 成群。其中Ta=( cosa sind sina cosa TbTa=cosb sinb cosa sina sinb cosb -sina cosa
4.1 群的概念 (2) 简单例子 例 G={1,-1}在普通乘法下是群。 例 G={0,1,2,…,n-1}在mod n的加法下是群. 例 二维欧氏空间所有刚体旋转T={Ta}构 成群。其中Ta = cosa sina -sina cosa TbTa= cosb sinb cosa sina -sinb cosb -sina cosa
4.1群的概念 cosacosb-sinasinb sinacosb-tcosasinb sinacos6-cosasinb cosacos6-sinasin6 coS(a+b) sin(a+b)=Tatb sin(a+b)cos(a+b) 从而有(a)封闭性 b)结合律成立: (TaTB)Ty=T(TT7)= TaTBTY;(c)有单位元: ()有逆元:Ta=Ta 0 cosa -sind sina cosa
4.1 群的概念 = cosacosb-sinasinb sinacosb+cosasinb -sinacosb-cosasinb cosacosb-sinasinb = cos(a+b) sin(a+b) =Ta+b -sin(a+b) cos(a+b) 从而有(a)封闭性; (b)结合律成立： (TαTβ)Tγ = Tα(TβTγ) = TαTβTγ ; (c)有单位元： T0 = ; (d)有逆元：Ta =T-a = cosa -sina sina cosa 1 0 0 1
4.1群的概念 前两例群元素的个数是有限的,所以是 有限群;后一例群元素的个数是无限的, 所以是无限群。 ·有限群G的元素个数叫做群的阶,记做|Gl。 若群G的任意二元素a,b恒满足ab=ba。责 称G为交换群,或Abel群 设G是群H是G的子集若H在G原有的运 算之下也是一个群,则称为G的一个子群
4.1 群的概念 • 前两例群元素的个数是有限的，所以是 有限群；后一例群元素的个数是无限的， 所以是无限群。 • 有限群G的元素个数叫做群的阶,记做|G|。 • 若群G的任意二元素a,b恒满足ab=ba。责 称G为交换群，或Abel群。 • 设G是群,H是G的子集,若H在G原有的运 算之下也是一个群,则称为G的一个子群
4.1群的概念 基本性质 (a)单位元唯一ee2=e2=e (b)消去律成立ab=ac→b=c, ba=ca→b=c (c)每个元的逆元唯一al=aa=e, ab= ba =e aa =ab a= b d(ab.c)=c.ba c.ba ab. c=e
4.1 群的概念 • 基本性质 (a)单位元唯一 e1e2=e2=e1 (b)消去律成立 ab=ac → b=c, ba=ca → b=c (c)每个元的逆元唯一 aa =a a = e, ab = ba = e , aa = ab , a = b (d)(ab….c) =c …b a . c …b a ab…c = e -1 -1 -1 -1 -1 -1 -1 -1 -1 -1 -1
4.1群的概念 (e)G有限,a∈G,则存在最小正整数r,使 得a=e且al=a 证设Gg则a2.,246G,由鸽巢原理 其中必有相同项。设理=a1,1≤m<1≤g+1, e默有正整数使得a=e其中必有最小 m,1≤1m≤g,令l-m则有ae即a a 者,不妨仍设为r.r称为a的阶。易见 H={a,a2aa=e}在原有运算下也是一个 群
4.1 群的概念 (e) G有限，a∈G，则存在最小正整数r，使 得a = e.且a = a . 证 设|G|=g,则a,a ,…,a ,a ∈G,由鸽巢原理 其中必有相同项。设a =a ,1≤m＜l≤g+1, e=a ,1≤l-m≤g，令l-m=r.则有a =a a=e.即a =a .既然有正整数r使得a =e,其中必有最小 者，不妨仍设为r. r称为a的阶。易见 H={a,a ,…a ,a =e}在原有运算下也是一个 群。 r -1 r-1 2 g g+1 m l l-m r r-1 -1 r-1 r 2 r-1 r
4.2置换群 置换群是最重要的有限群,所有的有限 群都可以用之表示。 置换:[1,n到自身的1-1变换。n阶置换。 [1n]目标集。(a12…a)aa.an是[1,n]中 元的一个排列。n阶置换共有n!个,同 置换用这样的表示可有n!个表示法。例 如p=(3134)=(3341),n阶置换又可看 作[1,n上的一元运算,一元函数
4.2 置换群 • 置换群是最重要的有限群，所有的有限 群都可以用之表示。 • 置换：[1,n]到自身的1-1变换。n阶置换。 [1,n]目标集。( ), a1a2…an是[1,n]中 元的一个排列。n阶置换共有n!个，同一 置换用这样的表示可有n!个表示法。例 如 p1=( )=( )，n阶置换又可看 作[1,n]上的一元运算，一元函数。 1 2 … n a1 a2 … an 1 2 3 4 3 1 2 4 3 1 4 2 2 3 4 1
4.2置换群 置换乘法P1=(3124),P2=(4321 PP2=( 1234Y3124 )=( 1234 3124人2431 注意:既然先做P的置换,再做P2的置换就规 定了若作为运算符或函数符应是后置的。这与 般习惯的前置不一样 般而言,对[,n]上的n阶置换,i[1,n要写成 (1)P1P 不是PP2(.(P有时写成i在上面例 中 322 P12343234,4231也 可写(1)PP2=2、(2)P1P2=43)PP2=3,4)PP2=1 P2P1=(4321)(4213)(4231)P1P2
4.2 置换群 • 置换乘法 P1=( ),P2=( ) P1P2=( )( )=( ) 注意：既然先做P1的置换，再做P2的置换就规 定了若作为运算符或函数符应是后置的。这与 一般习惯的前置不一样。 • 一般而言，对[1,n]上的n阶置换，i[1,n]要写成 (i)P1P2，而不是P1P2(i). (i)P有时写成i 在上面例 中，1→3→2,2→1→4,3→2→3,4→4→1.也 可写(1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1. P2P1=( )( )=( )≠P1P2. 1 2 3 4 3 1 2 4 1 2 3 4 3 1 2 4 1 2 3 4 4 3 2 1 3 1 2 4 2 4 3 1 1 2 3 4 2 4 3 1 P1 P2 P1 P2 P1 P2 P1 P2 1 2 3 4 4 3 2 1 4 3 2 1 4 2 1 3 1 2 3 4 4 2 3 1
4.2置换群 (1)置换群 [1,n上的所有n阶置换在上面的乘法定 义下是一个群 (a)封闭性(a2:(:2:)(b1b2Bn (b)可结合性( n al a2 aa2ahn八blb2 ab bi b2 n CI C2 (g12…a)=(a12…mn)( al a2 b1 b2. bi (c)有单位元e=(12…n n al a2.. an al a2. an n
4.2 置换群 • (1)置换群 [1,n]上的所有n阶置换在上面的乘法定 义下是一个群。 (a)封闭性 ( )( )=( ) (b)可结合性 (( )( ))( ) =( )=( )(( )( )) (c) 有单位元 e=( ) (d) ( ) =( ) 1 2 … n a1 a2 … an a1 a2 … an b1 b2 … bn 1 2 … n b1 b2 … bn 1 2 … n a1 a2 … an a1 a2 … an b1 b2 … bn 1 2 … n a1 a2 … an a1 a2 … an b1 b2 … bn 1 2 … n c1 c2 … cn b1 b2 … bn c1 c2 … cn b1 b2 … bn c1 c2 … cn 1 2 … n 1 2 … n 1 2 … n a1 a2 … an a1 a2 … an 1 2 … n -1