第四章P6lya定理 群的概念 置换群 循环、奇循环与偶循环 Burnside引理 Polya定理 例 母函数型的 Polya定理 图的计数
第四章 Pólya定理 • 群的概念 • 置换群 • 循环、奇循环与偶循环 • Burnside引理 • Pólya定理 • 例 • 母函数型的Pólya定理 • 图的计数
4.1群的概念 (1)群 定义给定集合G和G上的二元运算·,满足 下列条件称为群 (a)封闭性:若ab∈G,则存在ceG使得ab=c (b)结合律成立:任意ab,c∈G有(ab)c=a(bc) (c)有单位元:存在e∈G任意a∈Gae=ea=a (d有逆元:任意a∈G存在b∈G,ab=ba=e.b=a 由于结合律成立,(ab)c=a(b:c)可记做abc 例证明对于aa,,an的乘积,结合律成立 a°a°。。 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 sina 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 sinacosbtcosasinb sinacosb-cosasinb cosacosb-sinasinb coS(a+b)sin(a+b)=Ta+b sin(a+b)cos(a+b) 从而有(a)封闭性 (b)结合律成立 (TaTB)Ty=TIT7)= TaTTY;(c)有单位元: To 0g)有逆元:Ta=Ta cosa -sina 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的任意二元素ab恒满足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=el (b)消去律成立ab=ac→b=c, ba=ca→b=c (c)每个元的逆元唯一aal=aa=e, ab ba =e aa =ab a b (d)(ab =c, ba cba abc=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=c且a 证设G=g则aa2,aa2∈G由鸽巢原理 其中必有相同项。设a=a,1m<1≤g+1, e=a4m,1-lm≤g,令1m千则有a=e即a =a-既然有正整数r使得a=e其中必有最小 者,不e}在原有运算下也是一个 设为r.r称为a的阶。易见 Ha, a,...a 群
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阶置换。 [1,n]目标集。(a2…阻),aaam是[1,]中 元的一个排列。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 P1P2 1234Y3124 234 3124 2431 注意:既然先做P的置换,再做P2的置换就规 定了若作为运算符或函数符应是后置的。这与 般习惯的前置不一样。 般而言,对[n]上的n阶置换,i[n]要写成 P,而不是BPg2(①B有时写成在比面例 中 3-2.2-134.3323.441 也 可写(1)PP2=2,2)PP2=43)PP2=3、(4)P1P2=1 P2P1=(433)(4)=(4234)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
4.,2置换群 (1)置换群 [1n上的所有n阶置换在上面的乘法定 义下是一个群。 (a)封闭性( n yal a2 mn)=( aa2.an人bib2.bn b1 b2 bi (b)可结合性(a12…m)(2m):2) n al a2 an CI C2. C aa2.an八(blb2..bn人ci B…如n) (c)有单位元e=(12…m (d)(l132…an)=( an
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
