组合数学一节贝恩塞特引理与波利亚定理.pptVIP

* * 第4章 Burnside引理与Polya定理 4.1 群的概念 1 4.2 置换群 1 4.3 循环、奇循环与偶循环 1 4.4 Burnside引理 2 4.5 Polya 定理 3 4.6 举例 3 4.7 母函数形式的Polya定理 * 4.8 图的计数 * 4.9 Polya定理的若干推广 * 第四章 贝恩塞特引理与波利亚定理 一个田字格，用两种颜色染色，共有多少种方案？旋转能够重叠的算一种方案。 第四章 贝恩塞特引理与波利亚定理 C1 C2 C3 C4 C5 C6 C7 C8 C9 C10 C11 C12 C13 C14 C15 C16 4.1 群的概念 (a)封闭性: 4.1.1 群的定义: 给定一个集合G={a,b,c,...}和集合G上的二元运算“?”,并满足下列4个条件 (b)满足结合律: (c)存在单位元素 (d)存在逆元素 称集合G在运算“?”之下是一个群,有时也称G是一个群, 运算a?b简记为ab。 例4.1 对于任意两个整数,当除以n的余数相等时,说他们是相等的,或mod n相等. (a)封闭性成立 除以n的余数只能是0,1,2,...,n-1 (b)普通加法满足结合律 (c)0是单位元素 (d)对于任意a?G,a+(n-a)=0 modn 集合G={0,1,2,...,n-1}对mod n在加法下是一个群. n-a是a的逆。 4.1 群的概念 例4.2 设R={00,900,1800,2700,}表示几何图形绕轴心顺时针旋转角度的4种状态,设“?”是R上的二元运算,a?b表示平面图形连续旋转a和b得到的总旋转状态,并规定旋转3600等于原来的状态，也就是没有旋转。证明集合A在运算“?”构成一个群。 4.1 群的概念 180 90 0 270 270 90 0 270 180 180 0 270 180 90 90 270 180 90 0 0 270 180 90 0 (a)封闭性成立 (b)结合律成立 (c)0是单位元素 (d)逆原素存在 有限群G的元素个数叫做群的阶，记作?G? 当群的元素个数是有限时,称为有限群,当群的元素个数为无限时,称为无限群. 若群G的任意二元素a,b恒满足ab=ba时,称G为交换群,或Abel群。 有限群和无限群 交换群 4.1 群的概念 4.1.2 群的基本性质 定理4.1 群的单位元是唯一的 4.1 群的概念 定理4.2 ab=ac?b=c,ba=ca?b=c 定理4.3 G中每一个元素的逆元素是唯一的 定理4.4 定理4.5 G是有限群,h=?G?,设G={a1,a2,...,ah},设a是G的任意元素,则必存在一个最小正整数r(a),使得 ar(a)=e 而且a-1=ar(a)-1 证明:h是群G的阶?G?,a?G, aar(a)-1=e,即a-1=ar(a)-1。 构造:a,a2,...,ah,ah+1共h+1项, 其中至少有两项相等,设am=an,m≠n ar(a)=e, 4.1 群的概念 设mn 取所有am=an,m≠n,m-n的最小值, 令m-n=r(a), 子群定义4.1 设G是群,H是G的子集,若H在G的原来定义的运算下也构成群,则称H为群G的子群。 例4.2 若x是群G的一个元素，存在一最小的正整数m，使xm=e，则称m为x的阶，试证：C={e,x,x2,…,xm-1} 是G的一个子群 证明： (1) 封闭性成立。 (2)结合律 (3)单位元(4)逆元素 4.1 群的概念 ***** 4.2 置换群 假定n个元素为1,2,3,...,n, 并且若i?j, ai?aj, i,j=1,2,...,n 若元素1被1到n中某一元素a1所取代,2被其中某一元素a2所取代，...,n被an所取代, 置换的定义 有限集合S到自身的一一对应称为S上的一个置换。 说明：只要对应一样，就是同一个置换 置换与表示方式或顺序无关 4.2 置换群 置换运算的定义 4.2 置换群 n个元素形成的置换集合在以上运算下形成一个群。 (1)封闭性 4.2 置换群 (2)结合律 4.2 置换群 (3)单位元（恒等置换）