第四章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的一个子群