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