组合数学讲义_Polya定理.pdfVIP

第四章 Burnside 引理与 Polya定理 郝聚涛 群的概念 置换群 循环、奇偶循环 Burnside引理 Pólya定理 举例 母函数型式的Pólya定理 图的计数 5.1 群的概念 5.1 群的概念 定义5.1 ：给定集合G和G上的二元运算(G, · )，满足下 定义5.1 ： 列条件称为群 封闭性：若a,b ∈G，则存在c ∈G,使得a·b=c 结合律成立：任意a,b,c ∈G，有(a·b)·c=a·(b·c) （semigroup） 有单位元：存在e ∈G，使得对于任意a ∈G 满足 a·e=e·a=a （monoid） 有逆元：任意a ∈G，存在b ∈G, a·b=b·a=e 。记b=a-1 （group） G={0,1,2,…,n-1}在mod n 的加法下是群 G={1,2,…,n-1}在mod n的乘法下是群iff n是素数 iff - - - - 二维欧氏空间所有刚体旋转={Ta}构成群 ⎛ ⎞ cos α sin α x ⎜x1 ⎟ ⎛ ⎞⎛ ⎞ T : ⎜ ⎟⎜ ⎟ α ⎜ ⎟ ⎜ ⎟⎜ ⎟ sin cos α α y ⎝y 1 ⎠ ⎝− ⎠⎝ ⎠ cos sin coscos( sin ) sin( ) β ⎛ β α⎞⎛ αα β ⎞ ⎛α β + + ⎞ T =⋅T ⎜ ⎟⎜ ⎟ ⎜ ⎟ β α ⎜ ⎟⎜ ⎟ ⎜ ⎟ sin cos sinsin( cos ) cos( ) β χ α αα β α β ⎝− ⎠⎝− − ⎠ ⎝+ + ⎠ T α β+ (1) : : T T