置换就是把n个元素做一个全排列。比如1， 2，3，4分别变成3，1，2，4，或者分别变成4，3，2，1。一般地，1变a1,2变a2,...的置换记为
置换实际上就是一一映射。在程序上，可以用一个数组f={a1,a2,...,an}来表示1~n的一个置换，其中f[i]表示元素i所映射到的数。这个f也可以看成是定义域和值域为{1，2，3，...，n}的函数，其中f(1) = a1, f(2）= a2, ... f(n) = an。由于不同的元素映射到不同的数，这个函数是可逆的。
置换之间定义乘法，对应于函数复合。比如置换f={1, 3,2} 和 g = {2, 1, 3},乘积fg = {2, 3, 1},因为各个元素的变化为1到1到2，2到3到3，3到2到1.在数学上函数复合总是满足结合律，所以置乘法也满足结合律，但是不满足交换律。
为了处理方便，常常把置换分解成循环的乘积，其中每个循环代表一些元素循环移位。
任意置换都可以这样分解，我们把每个元素看成一个结点，如果a变成b，连一条有向边a到b，则每个元素恰好有一个后继结点和一个前驱结点。借用图论中的术语就是每个点的出度和入度均为1。不难发现，这样的图只能是若干个有向圈，其中每个圈对应一个循环。
任取一个元素，顺着有向边走，最终一定会走成一个环，然后换一个没被访问过的元素如法炮制，直到所有元素都被访问过。
等价计数问题
给2×2方格中涂黑白两色，有几种方法？16种
如果规定逆时针旋转90度，180度，270度后相同的方案算一种，那么答案就变成6种
这样的问题称为等价计数问题。也就是说题目会定义一种等价关系，满足等价关系的元素看成同一类，只统计一次。
自反性：每个元素和他自身等价
对称性：如果A和B等价，则B和A等价
传递性：如果A和B等价，B和C等价，则A和C等价
Burnside引理：
对于一个置换f，若一个着色方案s经过置换后不变，称s为f的不动点。将f的不动点数目记为C(f)，则可以证明等价类数目为所有C(f)的平均值。
逆时针旋转0度
p1 = (1)(2)...(16) 不动点的个数为16个
逆时针旋转90度
p2 = (1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16) 不动点的个数为2个
逆时针旋转180度
p3 = (1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12)(13 15)(14 16) 不动点个数为4个
逆时针旋转270度
p4 = (1)(2)(3 4 5 6)(7 8 9 10)(11 12)(13 14 15 16) 不动点的个数为2个
不同等价类个数为（16 + 2 + 4 + 2）/ 4 = 6
Polya定理：
设G={p1, p2, ..., pg}是一个置换群，C(pk)是置换pk的循环个数，用m种颜色着色，着色方案数为
G为置换的总个数，m为颜色数，c(pi)置换pi的循环个数
同样的着色问题
逆时针旋转0度
p1 = (1)(2)(3)(4) 4个循环
逆时针旋转90度
p2 = (1 4 3 2) 1个循环
逆时针旋转180度
p3 = (1 3)(2 4) 2个循环
逆时针旋转270度
p4 = (1 2 3 4) 1个循环
由Polya：1/4（2^4 + 2^1 + 2^2 + 2^1) = 6