组合数学波利亚定理VIP专享VIP免费

第六章Pólya(波利亚)定理6.1群论基础普通代数主要涉及的计算对象为数，运算方式多为加、减、乘、除。本节将把运算对象扩展到一般的集合元素，运算方式也可以是多种多样，例如矩阵运算、集合的并、交、差运算等。换言之，我们要将研究对象及其运算和所要讨论的性质延伸到抽象代数的范畴。§6.1.1群的概念定义6.1.1给定非空集合G及定义在G上的二元运算“·”，若满足以下四个条件，则称集合G在运算“·”下构成一个群，简称G为一个群。：（1）封闭性：a，bG，则a·bG；（2）结合律：（a·b）·c＝a·(b·c)；（3）单位元：存在eG，对任意aG，有a·e＝e·a＝a；（4）逆元素：对任意aG，存在bG，使得a·b＝b·a＝e，称b为a的逆元素，记为a－。群的运算符“·”可略去，即a·b＝ab.群的运算并不要求满足交换律。如果某个群G中的代数运算满足交换律，则称G为交换群或Abel群。群的元素可以是有限个，叫作有限群；也可以是无限个，叫无限群。以|G|表示有限群中元素的个数，称为群的阶，那么当G为无限群时，可以认为|G|＝∞。例6.1.1偶数集，整数集Z，有理数集Q，实数集R，复数集C关于数的加法构成群，称为加法群。因为数的运算对加法满足要求（1）和（2）。其中的单位元为0，每个数a关于加法的逆元为：a－＝－a。但是，关于数的乘法，这些集都不构成群。因为在偶数集中关于普通乘法不存在单位元。而在Z、Q、R、C中，虽然关于普通乘法有单位元1，但数0没有逆元。例6.1.2不含零的有理数集Q1，实数集R1和复数集C1关于数的乘法构成群其中单位元为e＝1，数a的逆元为aa11。例6.1.3G＝{1，－1}关于乘法构成群单位元为e＝1，由于(－1)－1＝－1，所以数a＝－1的逆元为它自身。例6.1.4更一般情形，集合G1＝{e＝1}，G2＝{1，－1}，G3＝{1，231i，231i)}(1的3次根)，⋯，Gn＝{ak＝eik2/n|k＝0，1，⋯，n－1，i＝1}（n＝1，2，⋯）均关于乘法构成群。其中单位元为e＝1，设nineqin2sin2cos122，则元素ak＝qk的逆元为1ka＝q－k＝qn－k.例6.1.5G＝{0，1，⋯，n－1}在模n（即modn）的情况下关于加法运算构成群，当n为素数时，1G＝0G＝1n21,,,关于乘法运算也构成群。在群G中，单位元为0，元素Ga的逆元为－a或n－a。而在1G中，单位元则为1，a的逆元为naaamod11。但对于某些特殊元素，其逆是显然的，如111，11n1或1n。例6.1.6所有m*n矩阵关于矩阵加法，所有非奇异（即可逆）n阶矩阵关于矩阵乘法都构成群。前者是可交换的，后者是不可交换群。例6.1.7二维欧几里德空间的刚性旋转变换集合T＝{T}构成阿贝尔群。其中T、T的二元运算T*T定义为：先做T，再对其结果做βT。验证T：11yx＝cossinsincosyx（1）封闭性：T*T＝T＋T（2）结合律：显然，（3）单位元：T0对应矩阵为E＝1001（4）逆元素：（T）－1＝T－例6.1.8设G＝{f1＝x，f2＝1－x，f3＝1/x，f4＝1－1/x，f5＝1/(1－x)，f6＝1－1/(1－x)}，定义G上的二元运算，fi*fj＝fi(fj（x）)，则G构成群。（证）首先G，其次：（1）可以逐一验证fi*fj＝fi(fj（x）)G；（2）同样可以逐一验证：fi*(fj*fk)＝(fi*fj)*fk；（3）单位元为f1＝x；（4）f4，f5互为逆元，其他fi的逆元是自身。§6.1.2群的性质定理6.1.1群具有以下性质（1）单位元e唯一；（2）逆元唯一；（3）满足消去律：即对a，b，cG，若ab＝ac，则b＝c；若ba＝ca，则仍有b＝c；（4）a，bG，则(ab)－1＝b－1a－1，更一般有(ab⋯c)－1＝c－1⋯b－1a－1；（5）若G是有限群，则对任意aG，必存在一个最小常数r，使ar＝e，从而11raa。r称为元素a的阶。（证）性质（1）～（4）显然。只证明性质（5）。设|G|＝n，由G的定义知.iiaaaa个＝aiG，i＝1，2，⋯，n＋1由抽屉原理知，必存在整数m，k，满足1≤m