第四章P6lya定理 群的概念 置换群 循环、奇循环与偶循环 Burnside引理 P6lⅤa定理 例 母函数型的Plya定理 图的计数
第四章 Pólya定理 • 群的概念 • 置换群 • 循环、奇循环与偶循环 • Burnside引理 • Pólya定理 • 例 • 母函数型的Pólya定理 • 图的计数
41群的概念 (1)群 定义给定集合G和G上的二元运算·,满足 下列条件称为群。 (a)封闭性:若ab∈G,则存在c∈G使得ab=c (b)结合律成立:任意abc∈G,有(ab)c=a(bc c)有单位元:存在eeG任意a∈Gae=ea=a (d)有逆元:任意a∈G存在b∈G,ab=ba=e.b 由于结合律成立,(ab)c=a(b)可记做abc 例证明对于a,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=({1,-1}在普通乘法下是群。 例G={0,1,2,…,n-1}在modn的加法下是群 例二维欧氏空间所有刚体旋转T={Ta}构 成群。其中Ta=( cosa sind sina cosa TbTa=cosb sinb(cosa sina sinb cosbl-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 sinacos6tcosasinb sinacosb-cosasinb cosacosb-sinasinb cos(a+b) sin(a+b)=Tatb sin(a+b)cos(a+b) 从而有(a)封闭性; (b)结合律成立: (lIB)Iy= Ta(TpT7)=TpTy;(c)有单位元: T ()有逆元:Ta=Ta 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的元素个数叫做群的阶,记做G|。 若群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)单位元唯 e1e2-e2-e1 (b)消去律成立ab=ac→b=c, ba=ca→>b=c (c)每个元的逆元唯一aa=aa=e ab= ba=e aa =ab a =b (d(ab.c)=c.ba baab.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
41群的概念 (e)G有限,a∈G,则存在最小正整数r,使 得 a=e且al=a 证设G=g则a2,a2∈G由鸽巢原理 其中必有相同项。设=a1,1≤m<1≤g+1, e=am,1≤lm≤g,令-m=则有a=he即a =a-既有正整数r使得a=e其中必有最小 者,不妨仍设为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置换群 置换群是最重要的有限群,所有的有限 群都可以用之表示。 置换:[1n]到自身的1-1变换。n阶置换。 [1n]目标集。(a…m)aa.n是[1n]中 元的一个排列。n阶置换共有n个,同 置换用这样的表示可有n!个表示法。例 如p=(3124)=(341),m阶置换又可看 作[1n]上的一元运算,一元函数
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
42置换群 置换乘法P=(3124)P2=(43 PP2=( 124 )=( 1234 3124八2431 注意:既然先做P的置换,再做P2的置换就规 定了若作为运算符或函数符应是后置的。这与 般习惯的前置不一样 般而言,对[1,n]上的n阶置换,1n要写成 j)PP2而不是PP2(.(P有时写成i在上面例 中,132,2124,3222341421.也 可写(1)PP2=22)PP2=43)PP2=3(4)PP2 P2P](4321)(4213)=(4231)PP
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
42置换群 (1)置换群 ,n上的所有n阶置换在上面的乘法定 义下是一个群 (a)封闭性(a2:2):m)(b2 (b)可结合性(2…m)(152m)h . n(al az2… an (b1 b2.b CI C2. C al a2. a b1 b2 bl (c)有单位元e=(2m) 2.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