《Burnside引理和Pólya定理》由会员分享，可在线阅读，更多相关《Burnside引理和Pólya定理（55页珍藏版）》请在金锄头文库上搜索。
1、,1,2,整点问题,这类平面上坐标都是整数的点称为整点，或者格点（lattice point)3.53 三维空间9个整点,试证在两两相连的线段内,至少有一个坐标为整数的内点证明：令9个点的坐标分别为（xi,yi,zi）,i=1,2,9 对于x1,x2,x9必有9/2=5个奇偶性相同，令为x1,x2,x5 对于y1,y2,y5必有5/2 =3个数奇偶性相同，令为y1,y2,y3 对于z1,z2,z3必有3/2 =2个数奇偶性相同，令为z1,z2。 则（x1,y1,z1）,(x2,y2,z2)连成的线段中点为一个整点，即这条线段有一个整点的内点。,3,在平面直角坐标系中至少任取多少个整点（两个坐标
2、都是整数）才能保证其中存在3个构成三角形（包含3点在一条直线上）的面积是整数（可以为0）解任一点的坐标（a , b）只有如下种可能：(奇数，偶数)、(奇数，奇数)、(偶数，奇数)、(偶数，偶数)。因而5个点中必有两个点模2的格式一样设2(x1x2)，2(y1y2)即x1x22k, y1y2l，则三角形面积,S,为整数,命题得证.,S,4,整点问题,在平面直角坐标系中至少任取多少个整点（两个坐标都是整数）才能保证其中存在3个构成三角形（包含3点在一条直线上）的面积是整数（可以为0）任一点的坐标（a , b）只有如下种可能：(奇数，偶数)、(奇数，奇数)、(偶数，奇数)、(偶数，偶数)。因而5个点
3、中必有两个点模2的格式一样设2(x1x2)，2(y1y2)三角形1的面积(x2-x1)*(y2-y1)/2三角形2的面积(x3-x2)*(y2-y3)/2三角形3的面积(x3-x1)*(y1-y3)/2矩形的面积(x3-x1)*(y2-y3)三角形S的面积=(x3(y2-y1)+y3(x1-x2)-x1y2+x2y1)/2 = (x3(y2-y1)+y3(x1-x2)-x1y2+x2y1 + x2y2-x2y2)/2 =(x3-x2)(y2-y1)+(y3-y2)(x1-x2)/2为整数,钝角三角形与直角三角形类似，则命题得证,5,在平面直角坐标系中至少任取多少个整点才能保证存在3个点构成的三
4、角形的重心是整点？解设(x，y)是整点，每个分量模3后有如下表的结果：,根据个点重心是整点的情况:1. 落在上表中的同一格中，2.若有点占满一行，3.有点占满一列，4.若存在一组均匀分布(每行取一个,每列取一个) 。如(0,0)(1,1)(2,2),若只有8个点，也不能保证有点的重心是整点（因为若每个格子都有点，则只占有个格子，无法保证上面的要求）,整点问题,6,考虑9个点的情况:假设存在个点，其中任点的重心都不是整点则这9个点，至少占有9/25个格子（因为每格中最多有2个点，否则有3个点的重心为整点），每行最多有格，有5/2=3行, 所以每行都有点,同理，每列都有点不妨设第一行2格，第二行2
5、格，第三行1格,前2 行有两种模式：这样第三行的点无论在哪一列都构成占满一列或构成一组均匀分布满足前面说的三点重心是整点的情况故 9个点能保证其中存在个点的重心是整点,整点问题,(0，0) (0，1) (0，2),(1，0) (1，1) (1，2),(2，0) (2，1) (2，2),7,平面上任何4n-3个整点中必可取出n个整点使其重心仍为整点?1983年Kemnitz猜想，用初等方法是无法解决这一困难猜想的。2000年有人使用代数方法成功地证明4n-3换成4n-2时猜想正确。2003年德国Reiher出人意料地将代数方法与组合方法巧妙地结合起來，攻下有20年之久的Kemnitz猜想,整点问
6、题,8,第四章 Burnside引理和Plya定理,马昱春清华大学计算机系,9,第四章 Burnside引理和Plya定理,组合计数中遇到的困难找出问题通解的表达式困难引入母函数区分讨论的问题类型困难,区分同类性,避免重复和遗漏容斥原理避免重复计数如何区分同类举例红蓝两种颜色给正方形的四个顶点着色,存在多少种不同的方案? 24若允许正方形转动,有多少种方案?分类：按红色点分类0个红点 1种1个红点 1种2个红点 2种3个红点 1种4个红点 1种,共6种,10,4.1 群的概念,群论群论是法国传奇式人物伽罗瓦（ Galois，18111832年）的发明。他用该理论，具体来说是伽罗瓦群，解决了五次
7、方程问题。伽罗华在圣佩拉吉监狱中写成的研究报告中写道：“把数学运算归类，学会按照难易程度，而不是按照它们的外部特征加以分类，这就是我所理解的未来数学家的任务，这就是我所要走的道路。”,11,伽罗华（Galois）,variste Galois(18111832) 引入群论新名词并奠定了群论基础非常彻底地把全部代数方程可解性问题，转化或归结为置换群及其子群结构分析的问题,得出五次以上一般代数方程根式不可解，以及用圆规、直尺(无刻度的尺)三等分任意角和作倍立方体不可能等结论。刘维尔在1846才领悟到其手稿中迸发出的天才思想，他花了几个月的时间试图解释它的意义 笛卡尔说过的那样：“在讨论超前的问题时
8、务必空前地清晰。” 他被公认为数学史上两个最具浪漫主义色彩的人物之一 他的死使数学的发展被推迟了几十年 这个人是上帝派来的，在人世间匆匆转了一圈，仅仅21年，却一不小心，开启了数学的一个新时代 .http:/ 群的概念,(1)群(group)定义 给定集合G和G上的二元运算 ，满足下列条件称为群。(a)封闭性(Closure)：若a,bG,则存在cG,使得ab=c.(b)结合律(Associativity)：任意a,b,cG,有(ab)c=a(bc).由于结合律成立，(ab)c=a(bc)可记做abc.(c)有单位元(identity)：存在eG,任意aG.ae=ea=a.(d)有逆元(inv
9、erse)：任意aG,存在bG, ab=ba=e. 记为b=a-1.,13,4.1 群的概念,(2) 简单例子例 G=1,-1在普通乘法下是群。证：1)封闭性：11=1 (-1)(-1)=1 (-1)1=-1 1(-1)=-1 2)结合律：成立 3)单位元：1 4)逆元素：1的逆元是1，-1的逆元是-1例 G=0,1,2,n-1在mod n的加法下是群.证：1)封闭性：除以n的余数只能是0,1,2,n-1，故封闭性成立 2)结合律：成立 3)单位元：0 4)逆元素：对任意元素a有(a+(n-a) mod n = 0 ,a的逆元a-1=n-a,14,4.1 群的概念,证：1)封闭性： 2)结合律
10、：成立(TT)T = T(TT) = TTT 3)单位元：T0 = 4)逆元素：Ta的逆元即T-a,15,4.1 群的概念,前两例群元素的个数是有限的，所以是有限群；后一例群元素的个数是无限的，所以是无限群。有限群G的元素个数叫做群的阶,记做|G|。若群G的任意二元素a,b恒满足ab=ba。责称G为交换群，或Abel群。设G是群,H是G的子集,若H在G原有的运算之下也是一个群,则称为G的一个子群。,16,4.1 群的概念,单位元唯一 e1e2=e2=e1消去律成立 ab=ac b=c, ba=ca b=c每个元的逆元唯一 aa-1=a-1a = e,ab-1 = ba-1 = e , aa-1
11、 = ab-1 , a-1=b(d)(ab.c)-1 = c-1 b-1a-1 . c-1 b-1a-1.abc = e,17,4.1 群的概念,(e) G有限，aG，则存在最小正整数r，使得ar = e.且a-1 = ar-1 .证 设|G|=g,则a,a2 ,ag,ag+1G,由鸽巢原理其中必有相同项。设am =al, 1mlg+1, e=al-m ,1l-mg，令l-m=r.则有ar =ar-1a=e.即a-1=ar-1.既然有正整数r使得ar =e,其中必有最小者，不妨仍设为r. r称为a的阶。易见 H=a,a2 ,ar-1 ,ar =e在原有运算下也是一个群。,18,4.2 置换群,
12、置换群是最重要的有限群，所有的有限群都可以用之表示。,19,4.2 置换群,置换乘法 P1=( ),P2=( )P1P2=( )( )=( ) P2P1=( )( )=( ). P2P1P1P2.置换不满足交换律但是满足结合律,1 2 3 43 1 2 4,1 2 3 43 1 2 4,1 2 3 44 3 2 1,3 1 2 42 4 3 1,1 2 3 42 4 3 1,1 2 3 44 3 2 1,4 3 2 14 2 1 3,1 2 3 44 2 1 3,20,4.2 置换群,(1)置换群(permutation group)1,n上的由多个置换组成的集合在上面的乘法定义下构成一个群,
13、则称为置换群。 (a)封闭性 ( )( )=( ) (b)可结合性 ( )( ) ( ) =( )=( )( ) ( ) (c) 有单位元 e=( ) (d) ( )-1 =( ),1 2 na1 a2 an,a1 a2 anb1 b2 bn,1 2 nb1 b2 bn,1 2 na1 a2 an,a1 a2 anb1 b2 bn,1 2 na1 a2 an,a1 a2 anb1 b2 bn,1 2 nc1 c2 cn,b1 b2 bnc1 c2 cn,b1 b2 bnc1 c2 cn,1 2 n1 2 n,1 2 na1 a2 an,a1 a2 an1 2 n,21,4.2 置换群,例 等边
14、三角形的转动群。不动绕中心转动120o绕对称轴翻转。,2,3,22,4.2 置换群,1,n上的所有置换(共n!个)构成一个群，称为n阶对称群(Symmetric group)，记做Sn.集合1，2，3的三个置换群组成S3注意：一般说1,n上的一个置换群，不一定是指Sn.但一定是Sn的某一个子群。,23,4.2 置换群,群同态(Group homomorphism )给定两个群 (G, *) 和 (H, )，从 (G, *) 到 (H, ) 的群同态是函数 h: G H 使得对于所有 G 中的 u 和 v 下述等式成立h(u * v) = h(u) h(v)双射(Bijection):一由集合X至集合Y的函数称为双射的，若对每一在Y内的y，存在唯一一个在X内的x，使得f(x)=y。换句话说，f为双射的若其为两集合间的一对一对应，亦即同时单射且满射。双射函数亦称为置换单射(Injection):函数f被称为是单射的，当对每一集合Y内的y，存在至多一个定义域内的x使得f(x)=y。满射(surjection ):一个函数为满射，对于任意的集合Y中的y，在函数的定义域X中存在至少一个x满足f(x) = y。,
