置换群在计数中的应用PPT课件.ppt

置换群在计数中的应用 净听我瞎扯淡吧 笑 1 1 你要知道置换群是什么鬼 2 一 置换群的基本概念定义1任一集合A到自身的映射都叫做的A一个变换 如果A是有限集且变换是一一变换 双射 那么这个变换为A的一个置换 有限集合A的若干个置换若作成群 就叫做置换群 含有n个元素的有限群A的全体置换作成的群 叫做n次对称群 通常记为Sn 3 置换群是一种特殊的变换群 换句话说 置换群就是有限集上的变换群 由于是定义在有限集上 故每个置换的表现形式 固有特点都是可揣测的 大家应该知道什么是变换群吧 封闭性 可结合 有单位元 存在逆元 4 5 6 举个栗子 7 p119 8 9 关于循环置换 10 2 这个置换群在计数中到底有什么应用 11 等价类计数 12 瞅一道题吧 用6种不同颜色给正方体的六个面着色 每个面有6中选择 假如给定每个面的编号 不同的着色序列有6 720 个 但哪些是 真正 不同的 因此 不同的着色有6 6 3 6 8 1 30种 13 其实我并没有看太明白 14 接下来我就要介绍一种简单粗暴的方法 15 16 如果不是每个面的着色都不同 比如有两个面是红的 如何判断两种着色是 真正 不同 设着色对象的集合是S 允许使用的颜色的集合是C 我们只考虑有限集 一种着色方案就是一个函数f S C f与f2被认为 实际上 是一样的 当且仅当在所允许的变换 即前面例子中的对称旋转 下 f1能转变为f2或相反 而对称旋转即置换群的元素 我们称 置换 群作用于S 也作用于C 其实我们看一下群与对称更好额 17 比立方体简单一点的例子 3个黑珍珠和6个白珍珠能做出多少样式不同的项链 18 置换群诱导的等价关系 假设G是集合X上的置换群 定义X上的关系 如下 x y X x y g G 使得g x y 是等价关系自反性 置换群中的单位元素一定是恒等映射 对称性 由群的逆元素性保证 传递性 由群的封闭性保证 将关系 所决定的等价类记为Gx Gx y y X 且 g G 使得g x y 这样的等价类称为X上G的轨道 19 保持x不变的置换构成子群 G中所有 将x变为y 的置换构成的集合 G x y g g G 且g x y G中所有 保持x不变 的置换的集合 Gx g g G 且g x x 注意 Gx构成子群 只需证明封闭性 G x y 是Gx的右陪集 h G x y G x y Gxh若 Gxh 令 h Gx 则 x X x h x h x y G x y 若 G x y 则 x X h 1 x h 1 y x 即 h 1 Gx Gxh 20 轨道的大小 子群与相应的陪集等势 因此 若y Gx G x y Gx 否则 G x y 0 对任意x X x所在的轨道的大小与保持x不变的置换的个数的乘积与x无关 给定x X 构造如下的矩阵 y g g行y列有 表示 g x y 对 计数 按行数 每行恰有1个 总数为 G 按列数 若某个y Gx 则该列恰有 G x y Gx 个 否则为空列 所以 Gx Gx G 21 y Gx Gy 值与所在轨道无关 对任意的y X 若y Gx 则 Gx Gy 实际上 G x y 是Gy的左陪集 即 h G x y G x y hGy若 hGy 令 h Gy 则 x X x h x y y G x y 若 G x y 则 y X h 1 y x y 即h 1 Gy hGy所以 对每个轨道 y Gx Gy Gx Gx G y Gx Gy 是 一个轨道中保持各元素不变的置换的总数 22 轨道的个数 令轨道数为t 因为每个轨道中保持各元素不变的置换的总数均为 G x X Gx t G F g 表示在置换g之下保持不变的x的个数 计算 g G F g 显然比计算 x X Gx 容易 而且 g G F g x X Gx 利用下列矩阵计数 x g g行x列有 表示 g x x 按行算 每行 数是在置换g之下不变的x的个数 总数即 g G F g 按列算 每列 数是保持特定x不变的置换的个数 总数即 x X Gx 23 Burnside定理 x X Gx t G g G F g x X Gx 於是 24 25 26 项链问题的解 3个黑珍珠和6个白珍珠能做出多少样式不同的项链 X 84 即C93 Why G 189个旋转 2个翻转对每个翻转g F g 4旋转0 的 F g 84 旋转120 和240 的 F g 各为3 其它均为0 结果是 4 9 84 3