《卢开澄组合数学--组合数学第四章》由会员分享，可在线阅读，更多相关《卢开澄组合数学--组合数学第四章（12页珍藏版）》请在金锄头文库上搜索。
1、第四章 Plya定理 群的概念 置换群 循环、奇循环与偶循环 Burnside引理 Plya定理 例 母函数型的Plya定理 图的计数Date组合数学4.1 群的概念 (1)群 定义 给定集合G和G上的二元运算 ，满足 下列条件称为群。 (a)封闭性：若a,bG,则存在cG,使得ab=c. (b)结合律成立：任意a,b,cG,有(ab)c=a(bc). (c)有单位元：存在eG,任意aG.ae=ea=a. (d)有逆元：任意aG,存在bG, ab=ba=e. b=a. 由于结合律成立，(ab)c=a(bc)可记做abc.例 证明对于a1,a2,an的乘积，结合律成立. aaa=a (共n个a相
2、乘).-1nDate组合数学4.1 群的概念(2) 简单例子 例 G=1,-1在普通乘法下是群。 例 G=0,1,2,n-1在mod n的加法下是群. 例 二维欧氏空间所有刚体旋转T=Ta构 成群。其中Ta = cosa sina-sina cosaTbTa= cosb sinb cosa sina -sinb cosb -sina cosaDate组合数学4.1 群的概念= cosacosb-sinasinb sinacosb+cosasinb-sinacosb-cosasinb cosacosb-sinasinb = cos(a+b) sin(a+b) =Ta+b-sin(a+b) cos
3、(a+b) 从而有(a)封闭性; (b)结合律成立： (TT)T = T(TT) = TTT ; (c)有单位元： T0 = ; (d)有逆元：Ta =T-a = cosa -sinasina cosa1 0 0 1Date组合数学4.1 群的概念 前两例群元素的个数是有限的，所以是 有限群；后一例群元素的个数是无限的 ，所以是无限群。 有限群G的元素个数叫做群的阶,记做|G| 。 若群G的任意二元素a,b恒满足ab=ba。责 称G为交换群，或Abel群。 设G是群,H是G的子集,若H在G原有的运 算之下也是一个群,则称为G的一个子群 。Date组合数学4.1 群的概念 基本性质(a)单位元唯
4、一 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 abc = e-1-1-1-1-1-1-1 -1-1-1 -1Date组合数学4.1 群的概念(e) G有限，aG，则存在最小正整数r，使 得a = e.且a = a . 证 设|G|=g,则a,a ,a ,a G,由鸽巢原理 其中必有相同项。设a =a ,1mlg+1, e=a ,1l-mg，令l-m=r.则有a =a a=e.即a =a .既然有正整数
5、r使得a =e,其中必有最小 者，不妨仍设为r. r称为a的阶。易见 H=a,a ,a ,a =e在原有运算下也是一个 群。r-1r-1 2gg+1mll-mrr-1 r-1-1r2r-1 rDate组合数学4.2 置换群 置换群是最重要的有限群，所有的有限 群都可以用之表示。 置换：1,n到自身的1-1变换。n阶置换。 1,n目标集。( ), a1a2an是1,n中 元的一个排列。n阶置换共有n!个，同一 置换用这样的表示可有n!个表示法。例 如 p1=( )=( )，n阶置换又可看 作1,n上的一元运算，一元函数。1 2 na1 a2 an1 2 3 43 1 2 43 1 4 22 3
6、4 1Date组合数学4.2 置换群 置换乘法 P1=( ),P2=( ) P1P2=( )( )=( ) 注意：既然先做P1的置换，再做P2的置换就规 定了若作为运算符或函数符应是后置的。这与 一般习惯的前置不一样。 一般而言，对1,n上的n阶置换，i1,n要写成 (i)P1P2，而不是P1P2(i). (i)P有时写成i 在上面例 中，132,214,323,441.也 可写(1)P1P2=2,(2)P1P2=4,(3)P1P2=3,(4)P1P2=1. P2P1=( )( )=( )P1P2.1 2 3 43 1 2 4 1 2 3 43 1 2 41 2 3 44 3 2 1 3 1
7、2 42 4 3 11 2 3 42 4 3 1P1P1P2P1P1P2P2P21 2 3 44 3 2 14 3 2 14 2 1 31 2 3 44 2 3 1Date组合数学4.2 置换群 (1)置换群 1,n上的所有n阶置换在上面的乘法定 义下是一个群。 (a)封闭性 ( )( )=( ) (b)可结合性 ( )( )( ) =( )=( )( )( ) (c) 有单位元 e=( ) (d) ( ) =( )1 2 na1 a2 ana1 a2 anb1 b2 bn1 2 nb1 b2 bn1 2 na1 a2 ana1 a2 anb1 b2 bn1 2 na1 a2 ana1 a2
8、anb1 b2 bn1 2 nc1 c2 cnb1 b2 bnc1 c2 cn b1 b2 bnc1 c2 cn1 2 n1 2 n1 2 na1 a2 ana1 a2 an1 2 n-1Date组合数学4.2 置换群 (2)例 等边三角形的运动群。绕中心转动120，不动，绕对称轴翻转。 P1=( ),P2=( ),P3=( ),P4=( ), P5=( ),P6=( )。 1,n 上的所有置换(共n!个)构成一个群，称为 对称群，记做Sn. 注意：一般说1,n上的一个置换群，不 一定是指Sn.但一定是Sn的某一个子群。1 2 3 1 2 31 2 3 2 3 11 2 3 3 1 21 2
9、3 1 3 21 2 3 3 2 11 2 3 2 1 312 3Date组合数学4.2 置换群 任一n阶群同构于一个n个文字的置换群 。设G=a1,a2,an，指定G中任一元ai, 任意ajG，Pi：aj aj ai ，则Pi是G上的 一个置换，即以G为目标集。 Pi=( )， G的右正则表示f：ai( )=Pi。f是单 射：aiaj，则PiPj f(aiaj) = ( ) =( )( )=f(ai)f(aj) 令P=Pi=( )|a,aiG,则PGa1 a2 ana1ai a2ai anaiai aaia1 a2 ana1(aiaj) a2(aiaj) an(aiaj)a1 a2 ana1ai a2ai anaia1 a2 an(a1ai)aj (a2ai)aj (anai)ajai aaiDate组合数学
