Burnside引理
设 (A) 和 (B) 为有限集合， (X=B^A) 表示所有从 (B) 到 (A) 的映射。 (G) 是 (A) 上的置换群， (X/G) 表示 (G) 作用在 (X) 上产生的所有等价类的集合（若 (X) 中的两个映射经过 (G) 中的置换作用后相等，则他们在同一等价类中），则
(|X/G|=frac{1}{|G|}sumlimits_{gin G}|X^g|) 其中 (X^g={x|xin X,g(x)=x})
Polya定理
设 (A) 和 (B) 为有限集合， (X=B^A) 表示所有从 (B) 到 (A) 的映射。 (G) 是 (A) 上的置换群， (X/G) 表示 (G) 作用在 (X) 上产生的所有等价类的集合（若 (X) 中的两个映射经过 (G) 中的置换作用后相等，则他们在同一等价类中），则
(|X/G|=frac{1}{|G|}sumlimits_{gin G}|B|^{c(g)}) 其中 (c(g)) 表示置换 (g) 能拆分成的不相交的循环置换的数量。
立方体染色问题
用3种不同的颜色给立方体染色，求本质不同的染色方案数（经过翻转后相同的两种方案视为同一种）。
(A) ：立方体6个面的集合。
(B) ：3种不同颜色的集合。
(X) ：所有的不考虑本质相同的染色方案的集合。每个面可以有3种不同的颜色，(|X|) 为 (3^6) 种。
(G) ：翻转操作构成的置换群。
(X/G) ：本质不同的染色方案的集合。
(X^g) ：对于一个特定的翻转操作 (g) ，(X) 中经过 (g) 的翻转后保持不变的染色方案的集合。
把立方体的初始状态的上下前后左右6个面分别标记为 (1,2,3,4,5,6) 号面。
(1) 号面朝上， (3) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 1 & 2 & 3 & 4 & 5 & 6 \ end{pmatrix}=
egin{pmatrix} 1\ 1\ end{pmatrix}egin{pmatrix} 2\ 2\ end{pmatrix}
egin{pmatrix} 3\ 3\ end{pmatrix}egin{pmatrix} 4\ 4\ end{pmatrix}
egin{pmatrix} 5\ 5\ end{pmatrix}egin{pmatrix} 6\ 6\ end{pmatrix} \
c(g)=6]
(1) 号面朝上， (4) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 1 & 2 & 4 & 3 & 6 & 5 \ end{pmatrix}=
egin{pmatrix} 1\ 1\ end{pmatrix}egin{pmatrix} 2\ 2\ end{pmatrix}
egin{pmatrix} 3 & 4\ 4 & 3\ end{pmatrix}egin{pmatrix} 5 & 6\ 6 & 5\ end{pmatrix} \
c(g)=4]
(1) 号面朝上， (5) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 1 & 2 & 5 & 6 & 4 & 3 \ end{pmatrix}=
egin{pmatrix} 1\ 1\ end{pmatrix}egin{pmatrix} 2\ 2\ end{pmatrix}
egin{pmatrix} 3 & 4 & 5 & 6\ 5 & 6 & 4 & 3\ end{pmatrix} \
c(g)=3]
(1) 号面朝上， (6) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 1 & 2 & 6 & 5 & 3 & 4 \ end{pmatrix}=
egin{pmatrix} 1\ 1\ end{pmatrix}egin{pmatrix} 2\ 2\ end{pmatrix}
egin{pmatrix} 3 & 4 & 5 & 6\ 6 & 5 & 3 & 4\ end{pmatrix} \
c(g)=3]
(2) 号面朝上， (3) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 2 & 1 & 3 & 4 & 6 & 5 \ end{pmatrix}=
egin{pmatrix} 1 & 2\ 2 & 1\ end{pmatrix}
egin{pmatrix} 3\ 3\ end{pmatrix}egin{pmatrix} 4\ 4\ end{pmatrix}
egin{pmatrix} 5 & 6\ 6 & 5\ end{pmatrix} \
c(g)=4]
(2) 号面朝上， (4) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 2 & 1 & 4 & 3 & 5 & 6 \ end{pmatrix}=
egin{pmatrix} 1 & 2\ 2 & 1\ end{pmatrix}
egin{pmatrix} 3 & 4\ 4 & 3\ end{pmatrix}
egin{pmatrix} 5\ 5\ end{pmatrix}egin{pmatrix} 6\ 6\ end{pmatrix} \
c(g)=4]
(2) 号面朝上， (5) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 2 & 1 & 5 & 6 & 3 & 4 \ end{pmatrix}=
egin{pmatrix} 1 & 2\ 2 & 1\ end{pmatrix}
egin{pmatrix} 3 & 5\ 5 & 3\ end{pmatrix}
egin{pmatrix} 4 & 6\ 6 & 4\ end{pmatrix} \
c(g)=3]
(2) 号面朝上， (6) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 2 & 1 & 6 & 5 & 4 & 3 \ end{pmatrix}=
egin{pmatrix} 1 & 2\ 2 & 1\ end{pmatrix}
egin{pmatrix} 3 & 6\ 6 & 3\ end{pmatrix}
egin{pmatrix} 4 & 5\ 5 & 4\ end{pmatrix} \
c(g)=3]
(3) 号面朝上， (1) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 3 & 4 & 1 & 2 & 6 & 5 \ end{pmatrix}=
egin{pmatrix} 1 & 3\ 3 & 1\ end{pmatrix}
egin{pmatrix} 2 & 4\ 4 & 2\ end{pmatrix}
egin{pmatrix} 5 & 6\ 6 & 5\ end{pmatrix} \
c(g)=3]
(3) 号面朝上， (2) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 3 & 4 & 2 & 1 & 5 & 6 \ end{pmatrix}=
egin{pmatrix} 1 & 2 & 3 & 4\ 3 & 4 & 2 & 1\ end{pmatrix}
egin{pmatrix} 5\ 5\ end{pmatrix}egin{pmatrix} 6\ 6\ end{pmatrix} \
c(g)=3]
(3) 号面朝上， (5) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 3 & 4 & 5 & 6 & 1 & 2 \ end{pmatrix}=
egin{pmatrix} 1 & 3 & 5\ 3 & 5 & 1\ end{pmatrix}
egin{pmatrix} 2 & 4 & 6\ 4 & 6 & 2\ end{pmatrix}\
c(g)=2]
(3) 号面朝上， (6) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 3 & 4 & 6 & 5 & 2 & 1 \ end{pmatrix}=
egin{pmatrix} 1 & 3 & 6\ 3 & 6 & 1\ end{pmatrix}
egin{pmatrix} 2 & 4 & 5\ 4 & 5 & 2\ end{pmatrix}\
c(g)=2]
(4) 号面朝上， (1) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 4 & 3 & 1 & 2 & 5 & 6 \ end{pmatrix}=
egin{pmatrix} 1 & 2 & 3 & 4\ 4 & 3 & 1 & 2\ end{pmatrix}
egin{pmatrix} 5\ 5\ end{pmatrix}egin{pmatrix} 6\ 6\ end{pmatrix} \
c(g)=3]
(4) 号面朝上， (2) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 4 & 3 & 2 & 1 & 6 & 5 \ end{pmatrix}=
egin{pmatrix} 1 & 4\ 4 & 1\ end{pmatrix}
egin{pmatrix} 2 & 3\ 3 & 2\ end{pmatrix}
egin{pmatrix} 5 & 6\ 6 & 5\ end{pmatrix} \
c(g)=3]
(4) 号面朝上， (5) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 4 & 3 & 5 & 6 & 2 & 1 \ end{pmatrix}=
egin{pmatrix} 1 & 4 & 6\ 4 & 6 & 1\ end{pmatrix}
egin{pmatrix} 2 & 3 & 5\ 3 & 5 & 2\ end{pmatrix}\
c(g)=2]
(4) 号面朝上， (6) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 4 & 3 & 6 & 5 & 1 & 2 \ end{pmatrix}=
egin{pmatrix} 1 & 4 & 5\ 4 & 5 & 1\ end{pmatrix}
egin{pmatrix} 2 & 3 & 6\ 3 & 6 & 2\ end{pmatrix}\
c(g)=2]
(5) 号面朝上， (1) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 5 & 6 & 1 & 2 & 3 & 4 \ end{pmatrix}=
egin{pmatrix} 1 & 3 & 5\ 5 & 1 & 3\ end{pmatrix}
egin{pmatrix} 2 & 4 & 6\ 6 & 2 & 4\ end{pmatrix}\
c(g)=2]
(5) 号面朝上， (2) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 5 & 6 & 2 & 1 & 4 & 3 \ end{pmatrix}=
egin{pmatrix} 1 & 4 & 5\ 5 & 1 & 4\ end{pmatrix}
egin{pmatrix} 2 & 3 & 6\ 6 & 2 & 3\ end{pmatrix}\
c(g)=2]
(5) 号面朝上， (3) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 5 & 6 & 3 & 4 & 2 & 1 \ end{pmatrix}=
egin{pmatrix} 1 & 2 & 5 & 6\ 5 & 6 & 2 & 1\ end{pmatrix}
egin{pmatrix} 3\ 3\ end{pmatrix}egin{pmatrix} 4\ 4\ end{pmatrix} \
c(g)=3]
(5) 号面朝上， (4) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 5 & 6 & 4 & 3 & 1 & 2 \ end{pmatrix}=
egin{pmatrix} 1 & 2 & 5 & 6\ 5 & 6 & 2 & 1\ end{pmatrix}
egin{pmatrix} 3 & 4\ 4 & 3\ end{pmatrix} \
c(g)=3]
(6) 号面朝上， (1) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 6 & 5 & 1 & 2 & 4 & 3 \ end{pmatrix}=
egin{pmatrix} 1 & 3 & 6\ 6 & 1 & 3\ end{pmatrix}
egin{pmatrix} 2 & 4 & 5\ 5 & 2 & 4\ end{pmatrix}\
c(g)=2]
(6) 号面朝上， (2) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 6 & 5 & 2 & 1 & 3 & 4 \ end{pmatrix}=
egin{pmatrix} 1 & 4 & 6\ 6 & 1 & 4\ end{pmatrix}
egin{pmatrix} 2 & 3 & 5\ 5 & 2 & 3\ end{pmatrix}\
c(g)=2]
(6) 号面朝上， (3) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 6 & 5 & 3 & 4 & 1 & 2 \ end{pmatrix}=
egin{pmatrix} 1 & 2 & 5 & 6\ 6 & 5 & 1 & 2\ end{pmatrix}
egin{pmatrix} 3\ 3\ end{pmatrix}egin{pmatrix} 4\ 4\ end{pmatrix} \
c(g)=3]
(6) 号面朝上， (4) 号面朝前
[g=egin{pmatrix} 1 & 2 & 3 & 4 & 5 & 6 \ 6 & 5 & 4 & 3 & 2 & 1 \ end{pmatrix}=
egin{pmatrix} 1 & 6\ 6 & 1\ end{pmatrix}
egin{pmatrix} 2 & 5\ 5 & 2\ end{pmatrix}
egin{pmatrix} 3 & 4\ 4 & 3\ end{pmatrix} \
c(g)=3]
Polya定理
[egin{align}
onumber|X/G|&=frac{1}{|G|}sumlimits_{gin G}|B|^{c(g)}\
onumber &=frac{1}{24}(8cdot 3^2+12cdot 3^3+ 3cdot 3^4+ 1cdot 3^6)\
onumber &= 57
end{align}]
验证
[洛谷P4980 Pólya 定理]
(n) 个环染最多 (m) 种颜色，求本质不同的染色方案数量（绕轴旋转之后不同就是不同）。
题解：绕轴旋转会把 (n) 恰好断成若干个相等的置换。绕轴旋转 (x) 次，若 (gcd(i,n)=g) ，则把原本的长度为 (n) 的置换断成了 (g) 个长度为 (frac{n}{g}) 的置换。
这样又引出一个新问题：
[egin{align}
onumber |X/G|&=frac{1}{n}sumlimits_{i=1}^{n} m^{gcd(i,n)}\
onumber &=frac{1}{n}sumlimits_{g|n} m^g sumlimits_{i=1}^{n}[gcd(i,n)=g]\
end{align}]
子问题：给定一个 (d,d|n) ，求 (sumlimits_{i=1}^{n}[gcd(i,n)=d]) 的值。
[sumlimits_{i=1}^{n}[gcd(i,n)=d]=sumlimits_{i=1}^{frac{n}{d}}[gcd(i,frac{n}{d})=1] varphi(frac{n}{d})
]
[egin{align}
onumber |X/G|&=frac{1}{n}sumlimits_{g|n} m^g varphi(frac{n}{g})\
end{align}]
[CF1065E Side Transmutation]
添加 (b_0=0) ，观察得到每一段区间 ([b_{i-1}+1,b_i]) 都可以单独抽出来和对位交换，总共 (m) 种单独的置换，他们构成了恰好 (m) 段可独立考虑的置换的区间，所以总共有 (2^m) 种置换。
单独考虑一个置换选择或者不选择，若这个区间长度为 (l_i) ，那么假如不选择这个区间，这个区间及其对位都可以自由染色，否则会减少 (l_i) 中颜色（对位要相同染色，只计算左边），那么答案就是 (frac{1}{2^m}A^nprodlimits_{i=1}^{m}(1+frac{1}{A^{l_i}}))
（其实每一种操作是独立的操作的时候，用Polya定理感觉有点大材小用，Polya定理可能还是解决正n边形、正n面体等翻转旋转等情形非常复杂但是总的方法种类不多的情形）