2/62
《组合数学》
第六章 波利亚定理
【例6.1.7】 二维欧几里德空间的刚性旋转变换集合 T＝{T } 构成阿贝尔群。其中T 、T 的二元运算T T 定义为：先做T ，
再对其结果做T 。
验证
T ：
x1 y1
c o s s i n
s c
i n o s
x y
（1）封闭性：T T ＝T T （2）结合律：显然，
（3）单位元：
T0对应矩阵为Fra bibliotekE＝1 0
0 1
（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 的逆元是自身。
1/62
《组合数学》
第六章 波利亚定理
但是，关于数的乘法，这些集都不构成群。因为在偶数集中 关于普通乘法不存在单位元。而在 Z、Q、R、C 中，虽然关于普 通乘法有单位元 1，但数 0 没有逆元。
【例6.1.2】 不含零的有理数集 Q1，实数集 R1 和复数集 C1
关于数的乘法构成群其中单位元为 e＝1，数 a 的逆元为 a 1 1 。 a
乘法构成群。
单位元：e＝1
设q
n
1
e2 i
2 ＝ cos
2 n
i sin
2 n
，则元素 ak
qk
的逆
元为 ak1 qk qnk 。
【例6.1.5】 G ＝{0，1，…，n－1}在模 n（即 mod n）的情 况下关于加法运算构成群，当 n 为素数时，G1 ＝G－{0}＝{1, 2, …， n－1}关于乘法运算也构成群。
aaa a i ＝ai G，i＝1，2，…，n＋1
i个
由抽屉原理知，必存在整数 m，k，满足 1≤m<k≤n＋1，使得 am ak ，即 ak m e，令 r＝k－m，则 ar ＝e，即 a ar1 ＝e，所以 a 1 a r1
（证）（1）a*b＝a＋b－2G；
（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）单位元为 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
＝(4－a)＋a－2 ＝(4－a)*a
群的运算符“·”可略去，即 a·b＝ab . 群的运算并不要求满足交换律。如果某个群 G 中的代数运算 满足交换律，则称 G 为交换群或 Abel 群。 群的元素可以是有限个，叫作有限群 ；也可以是无限个， 叫无限群。 以|G|表示有限群中元素的个数，称为群的阶，那么 当 G 为无限群时，可以认为|G|＝∞。 【例6.1.1】 偶数集，整数集 Z，有理数集 Q，实数集 R，复 数集 C 关于数的加法构成群，称为加法群。 因为数的运算对加法满足要求（1）和（2）。其中的单位元为 0，每个数 a 关于加法的逆元为： a 1 ＝－a。
在群 G 中，单位元为 0，元素 a G 的逆元为－a 或 n－a。
而在G1 中，单位元则为 1，a 的逆元为 a1 a a1（mod n）。
但对于某些特殊元素，其逆是显然的，如11 1 ，n 1 1 1或
n－1。
【例6.1.6】 所有 m*n 矩阵关于矩阵加法，所有非奇异（即 可逆）n 阶矩阵关于矩阵乘法都构成群。前者是可交换的，后者 是不可交换群。
§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－ 。
验证： f1 * fi f1 fi x fi x fi * f1 fi f1x fi x
3/62
《组合数学》
第六章 波利亚定理
f2 *
f3
f2 f3x
f2
1 x
1
1 x
f4x
f4 *
f5
f4 f5x 1
1 f5
1
1 1
x f1x
1 x
【例6.1.9】 设 G＝{全部整数}，a, bG，定义 a*b＝a＋b－ 2，则 G 关于运算*构成一个群。
（5）满足交换律：a*b＝a＋b－2＝b＋a－2＝b*a
§6.1.2 群 的 性 质
定理6.1.1 群具有以下性质 （1）单位元 e 唯一； （2）逆元唯一； （3）满足消去律：即对 a，b，c G，若 ab＝ac，则 b＝c； 若 ba＝ca，则仍有 b＝c；
4/62
《组合数学》
第六章 波利亚定理
《组合数学》
第六章 波利亚定理
第 六 章 P ól y a ( 波 利 亚 ) 定 理
6.1 群 论 基 础
普通代数：计算对象为数，运算方式多为加、减、乘、除。
扩展：计算对象为一般的集合元素，运算方式也可以是多种 多样。例如矩阵运算、集合的并、交、差运算等。
抽象代数：应用：代数、计数、通信编码、信息与网络安全 等。
【例6.1.3】 G＝{1，－1}关于乘法构成群
单位元为 e＝1
由于 1 1 ＝－1，所以数 a＝－1 的逆元为它自身。
【例6.1.4】 更一般情形，集合 G1＝{e＝1}，G2＝{1，－1}，
G3＝{1，
1
i 2
3 ，1i 2
3
)}
(1
的
3
次
根)，…，G
n＝{ak
＝e i k2 /n| k＝0，1，…，n－1，i＝ 1 }（n＝1，2，…）均关于
（ 4 ） a ， b G ， 则 ab 1 b1a1 ， 更 一 般 有 abc 1 c1 b1a1 ；
（5）若 G 是有限群，则对任意 aG，必存在一个最小常数 r， 使 ar＝e，从而 a1 ar1 。r 称为元素 a 的阶。
（证）性质（1）～（4）显然。只证明性质（5）。
设|G|＝n，由 G 的定义知.