《《组合数学》教案6章(波利亚定理)》由会员分享，可在线阅读，更多相关《《组合数学》教案6章(波利亚定理)（59页珍藏版）》请在金锄头文库上搜索。
1、组合数学 第六章 波利亚定理1/59 第六章 P l y a（ 波 利 亚 ） 定 理1. 群 论基础2. 置 换群及其应用3. Burnside引理及其在染色问题中的应用4. P lya 定理及其在染色问题中的应用5. 母 函数型的 P lya 定理及其应用（分类统计）6.1 群 论 基 础普通代数：计算对象为数，运算方式多为加、减、乘、除。扩展：计算对象为一般的集合元素，运算方式也可以是多种多样。例如矩阵运算、集合的并、交、差运算等。抽象代数：应用：代数、计数、通信编码、信息与网络安全等。 6.1.1 群 的 概 念【 定义 6.1.1】给定非空集合 G 及定义在 G 上的二元运算“ ”
2、，若满足以下四个条件，则称集合 G 在运算“ ”下构成一个群，简称 G 为一个 群 ：（ 1）封闭性： a， b G，则 a b G；（ 2）结合律： (a b) c a (b c)；（ 3）单位元：存在 e G，对任意 a G，有 a e e a a；（ 4）逆元素：对任意 a G，存在 b G，使得 a b b a e，称 b 为 a 的逆元素，记为 a 。群的运算符“ ”可略去，即 a b ab . 群的运算不要求满足交换律。否则称为为 交换群 或 Abel 群 。群的元素可以是有限个，叫作 有限群 ；也可以是无限个，叫 无限群 。 以 |G|表示有限群中元素的个数，称为群的 阶 ，那么
3、组合数学 第六章 波利亚定理2/59 当 G 为无限群时，可以认为 |G|。【 例 6.1.1】偶数集，整数集 Z，有理数集 Q，实数集 R，复数集 C 关于数的加法构成群，称为加法群。（证） （ 1）封闭性：（ 2）结合律：（ 3）单位元： 0 （ 4）逆元： 1a a。但是，关于数的乘法，这些集都不构成群。因为在偶数集中关于普通乘法不存在单位元。而在 Z、 Q、 R、 C 中，虽然关于普通乘法有单位元 1，但数 0 没有逆元。【 例 6.1.2】不含零的有理数集 Q1，实数集 R1 和复数集 C1 关于数的乘法构成群。单位元： e 1； a 的逆元：aa11 。【 例 6.1.3】 G 1
4、， 1关于乘法构成群单位元为 e 1； 11 1。【 例 6.1.4】 1 的 n 次方根关于乘法构成 n 阶循环群。（ 1） n 1， G1 e 1（即方程 x 1 的解）（ 2） n 2， G2 1, 1（即方程 2x 1 的解）（ 3） n 3，231,231,13iiG （ 即方程 3x 1的解 ）（ 4）一般情形：1;1,1,02 inkeaG nikkn单位元： e 1 组合数学 第六章 波利亚定理3/59 设 nin eq 21 nin2sin2cos ，则元素 kk qa 的逆元为 knkk qqa 1 。【 例 6.1.5】 G 0， 1， , ， n 1在模 n（即 mod
5、 n）的情况下关于加法运算构成群，当 n 为素数时， 1G G 0 1, 2, , ，n 1关于乘法运算也构成群（此时 G 构成域） 。在 G 中，单位元为 0，元素 Ga 的逆元为 a 或 n a。在 1G 中，单位元则为 1， a 的逆元为 11 aaa （ mod n） 。特殊元素的逆： 11 1 ， 11 1n 或 n 1。【 例 6.1.6】 所有 m*n 矩阵关于矩阵加法， 所有非奇异 （即可逆）n 阶矩阵关于矩阵乘法都构成群。前者是可交换的，后者是不可交换群。【 例 6.1.7】 二维欧几里德空间的刚性旋转变换集合 T T 构成阿贝尔群。其中 T 、 T 的二元运算 TT 定义为
6、：先做 T ，再对其结果做 T 。验证 T ：yxyxc oss i ns i nc os11（ 1）封闭性： TT T T （ 2）结合律：显然，（ 3）单位元： 0T 对应矩阵为 E 10 01（ 4）逆元素： TT 1【 例 6.1.8】 设 G 1f x， f2 1 x，xf13 ， xf114 ，xf 115 ， xf 1116 ，定义 G 上的二元运算， fi* fj fi( fj(x)，则 G 构成群。组合数学 第六章 波利亚定理4/59 （ 证 ）首先 G ，其次：（ 1） 可以逐一验证 fi* fj fi( fj(x) G ；（ 2） 同样可以逐一验证： fi* ( fj *
7、 fk) ( fi* fj) * fk；（ 3） 单位元为 f1 x；（ 4） f4 ， f5 互为逆元，其他 fi 的逆元是自身。验证： xfxffff iii 11 *xfxffff iii 11*xfxxfxffff 423232 111*xfxxfxffff 155454111111*【 例 6.1.9】 设 G 全部整数 ， a, b G，定义 a*b a b 2，则 G 关于运算 *构成一个群。（证） （ 1） a*b a b 2 G；（ 2） (a*b) *c (a*b) c 2 (a b 2) c 2 a (b c 2) 2 a (b*c) 2 a*(b*c) （ 3）单位元为
8、 2： a*2 a 2 2 a 2 a 2 2*a （ 4） a 的逆元为 a 4 4 a： a*(4 a) a (4 a) 2 2 (4 a) a 2 (4 a)*a （ 5）满足交换律： a*b a b 2 b a 2 b*a 组合数学 第六章 波利亚定理5/59 6.1.2 群 的 性 质【 定理 6.1.1】 群具有以下性质（ 1）单位元 e 唯一；（ 2）逆元唯一；（ 3）满足消去律：即对 a， b， c G，若 ab ac，则 b c；若 ba ca，则仍有 b c；（ 4 ） a ， b G ， 则 111 abab ， 更 一 般 有1111 abccab ；（ 5） 若 G
9、是有限群， 则对任意 a G， 必存在一个最小常数 r，使 ar e，从而 11 raa 。 r 称为元素 a 的 阶 。（证） （ 1）（ 4）显然。（ 5）设 |G| n，由 G 的定义知 . iiaaaa个 ai G， i 1， 2， , ， n 1 由抽屉原理知，必存在整数 m， k，满足 1 mk n 1，使得km aa ，即 mka e，令 r k m，则 ra e，即 1raa e，所以 11 raa 6.1.3 子 群【 定义 6.1.2】 设 G 是群， H 是 G 的子集，若 H 在 G 的原有运算下也构成一个群，则称 H 是 G 的 子群 。【 例 6.1.10】 任何群
10、 G 至少有两个子群： H1 G， H2 e| e G 为单位元 。【 例 6.1.11】 对于乘法运算， H 1， 1是 G 1， 1， i， i的子群。【 例 6.1.12】 偶数加法群是整数群 Z 的子群， Z 是有理数加法群 Q 的子群， Q 又是实数加法群 R 的子群， R 是复数加法群 C 的组合数学 第六章 波利亚定理6/59 子群；对乘法群而言，也有 Q1 是 R1 的子群， R1 是 C1 的子群。【 例 6.1.13】 任选群 G 的一个元素 a， 设 a 的阶为 r， 则 H a，a2， ， ar 1， ar e是 G 的子群。这样的群 H 是由某个固定元素a 的乘方组成
11、，称为 循环群 ，或称 H 是由元素 a 生成的群， a 叫作 H 的 生成元 。例如， G 1,2,3,4,5,6关于模 7 的乘法构成循环群，其生成元为 3 3 , 23 , 33 , 43 , 53 , 63 3， 2， 6， 4， 5， 1 另外，以 2 为生成元，可以得到 G 的一个子群H 2, 22 , 32 2,4,1 【 定理 6.1.2】 有限群的阶数必能被其子群的阶数整除。（ 证 ） （略） 。伽罗华 （ variste Galois， 1811 1832）简介：是法国对函数论、方程式论和数论作出重要贡献的数学家，他的工作为群论（一个他引进的名词）奠定了基础。源 自 他 尚
12、 在 校 就 读 时 欲 证 明 五 次 多 项 式 方 程 根 公 式 解（ Solution by Radicals） 的不可能性 （其实当时已为阿贝尔 （ Abel）所证明） ，和描述任意多项式方程可解性的一般条件的打算。于 1829 年将论文送交法兰西科学院时， 第一次所交论文却被柯西（ Cauchy）遗失了，第二次则被傅立叶（ Fourier）所遗失。第三次送交科学院的论文亦为泊松（ Poisson）所拒绝。伽罗华死于一次决斗，可能是被保皇派或警探所激怒而致。评论： “数学史上最年轻、 最富有创造性的头脑停止了思考” 。“他的死使数学的发展被推迟了几十年，他就是伽罗华” 。组合数学
13、第六章 波利亚定理7/59 6.2 置 换 群不论在理论研究还是在实际应用中，置换群都是十分重要的一类群。一方面，任何有限群都可以用它表示；另一方面，在解决“代数方程是否能用根号求解”这个问题时，要用到它；它还在本章的 Burnside引理及 P lya 定理中起着基本作用。（一）置换【 定义 6.2.1】 有限集合 S 到自身的一个映射叫做一个 置换 。例如 S a1， a2， a3， a4， p12424321aaaaaaaa即是一个置换。相应的映射是?： a1 ?(a4)， a2 ?(a1)， a3 ?(a3)， a4 ?(a2) . 或 ?： ?(a1) a2， ?(a2) a4， ?
14、(a3) a3， ?(a4) a1说明 ：（ 1）将 S 中的元素 ai 写在上一行（顺序可任意）， ai 的象写在 ai 之下，同一列的两个元素的相对关系只要保持不变，即iki aaf ，不同形式的写法都认为是同一个置换。如132321 321213 231123（ 2）置换就是将 n 个元的一种排列变为另一种排列。（ 3） n 元集 S 共有个 n!不同的置换。（二）置换的运算【 定义 6.2.2】 两个 置换 p1、 p2 的乘积 21 pp 定义为先做置换 p1再做 p2 的结果。组合数学 第六章 波利亚定理8/59 例 p142134321 ， p2 1234432121 pp 42
15、13432112344321 13424321即 1 1p 3 2p 2， 2 1p 1 2p 4，,一般来说，置换的乘法不满足交换律，即 p1p2 p2p1，如上例中12 pp 1234432142134321 31244321 21 pp技巧 （求复合置换）：更改 p2 各列的前后次序，使其第一行的排列与 p1 第二行的排列相同，则复合置换 21 pp 的第一行就是p1 的第一行，其第二行是 p2 的第二行。21 pp 42134321123443214213432113424213 13424321321 ppp 42134321314243211234432142134321213413421342421321344321【 定理 6.2.1】 设 Sn 是 n 元集合上的所有置换构成的集合，则Sn 关于置换的乘法构成 群，称为 n 次对称群 。（证）（ 1）封闭性：由置换乘法定义知组合数学 第六章 波利亚定理9/59 （ 2）结合律：显然成立（ 3）单位元（称为 恒等置换 ）： e nn.21 .21（ 4）逆
