参考论文

这一部分在黑书中， 是在群论这一部分介绍的 所以我们先了解什么是群

群的定义

给定一个集合G={a,b,c…}和集合G上的一个二元计算*，满足以下四个条件： （1）封闭性 若a,b∈G,则存在唯一确定的c∈G,使得a*b=c; （2）结合律成立 任意a,b,c∈G,有(a*b)* c=a* (b*c); （3）单位元存在 存在e∈G,对任意a∈G，满足a*e=e*a=a，称e为单位元，也称幺元; （4）逆元存在 任意a∈G,存在唯一确定的b∈G, a*b=b*a=e（单位元），则称a与b互为逆元素，简称逆元，记作a^(-1)=b.

通常称G上的二元运算*为“乘法”，称a*b为a与b的积，并简写为ab. 若群G中元素个数是有限的，则G称为有限群。否则称为无限群。有限群的元素个数称为有限群的阶。

置换的定义

n个元素1,2,3,4,…，n之间的一个置换为 表示1被1到n中的某一个数a1取代，2被1到n中的某一个数a2取代，直到n被1到n中的某一个数an取代，且a1到an各不相同

置换群 置换群的元素是置换，运算的置换的连接 可以验证置换群满足群的四个条件：

循环 记 称为n阶循环 每个置换都可以看作是若干互不相交的循环的乘积

为什么呢？因为我们可以把每个元素看作是一个结点， 如果a变成b，连一条有向边a—>b，则每一个节点一定有一个前驱结点和一个后继结点， 即每个点的出度和入度都为1，这样的图对应就是若干个环（轮换）

两个循环(a1 a2 … an) (b1 b2 … bn)互不相交是指 ai！=bj（i，j=1,2,3,4,…,n） 例： 挺好理解的吧

这样的表示是唯一的 置换的循环节数是上述表示中循环的个数 循环也称为轮换

对换 简单来说就是两个元素的交换

等价类计数问题 有这样一个经典问题，给2*2方格中涂黑白两色，有几种方案 Ans.16

但是如果定义一种“旋转操作”，规定逆时针旋转90°，180°，270°后相同的方案算作一种， 那么答案就变成6种了

这类问题被称作是等价类计数问题 也就是说，题目中会定义一种等价关系，满足等价关系的元素被看做是同一类 等价关系满足自反性和传递性

有了等价关系，所有的元素就会被分成若干等价类， 每个等价类里的所有元素相互等价，不同等价类里的元素不等价

为了统计等价类的个数 我们需要用一个置换集合F描述等价关系 比如说“逆时针旋转90°”这个置换就可以把映射到

对于一个置换f，若一个方案经过置换后不变，称s为f的不动点 将f的不动点的数目记为C(f)，则有

Burnside 定理

等价类数目为所有C(f)的平均值

例如在本题中， “逆时针旋转180°”的不动点： “逆时针旋转90°”的不动点： “逆时针旋转270°”的不动点： “逆时针旋转0°”的不动点：

根据Burnside引理，答案是（16+2+2+4）/4=6

如何求C(f)呢？ 我们先把格子编号 比如”逆时针旋转180°“这个置换就可以看作是轮换（1,3）（2,4）的乘积 即1,3互换，2,4互换 则如果是不动点的话，1和3的颜色一定要一样，2和4的颜色一定要一样 而这两和轮换不想交，所以互不影响，根据乘法原理一共有2*2=4种方案

一般的， 如果置换f被分解成m(f)个轮换，每个轮换内所有格子的颜色不必须相同， 假设有k种颜色，则有C(f)=k^m(f) 代入Burnside 定理表达式后得到Polya定理： 等价类个数等于所有置换f的k^m(f)的平均数

一定要记住Burnside引理，一般的等价类问题均可以用ta解决