(Preface)
群论里的东西。
感觉跟着论文一步步看下来还是挺好理解的吧。
前置知识
- 【莫比乌斯反演·入门篇】懵逼钨丝反演：和(Polya)定理的推导无关，但要做板子题就需要它。
群论的基本知识
群
群自然是群论中最为基础的定义。
若对于一个集合(G)以及一个给定的二元运算(*)，满足以下条件：
- 封闭性： (forall a,bin G,a*bin G)。
- 结合律： (forall a,b,cin G,(a*b)*c=a*(b*c))。
- 单位元： (exists ein G,forall ain G,a*e=e*a=a)。
- 逆元： (forall ain G,exists bin G,a*b=b*a=e)。
就称集合(G)在运算(*)之下是一个群。
置换群
置换群中的元素是置换（置换是什么相信大家都知道），运算就是置换的连接。
这是一个相对简单的概念，余就不多说了。
(Polya)定理的推导
公式：(|E_k| imes |Z_k|=|G|)
此处(G)是一个(1sim n)的置换群，而(k)是(1sim n)的某个元素。
(Z_k)（(k)不动置换类）： (G)中使(k)保持不变的所有置换记作(Z_k)。（简称(k)不动置换类）
(E_k)（等价类）：(k)在(G)的作用下能够变化得到的所有元素的集合记作(E_k)。
根据定义，其实很容易就能证明上面公式的正确性。
(Burnside)引理
首先介绍一个新的定义：
(D(a_j))：在置换(a_j)下不变的元素个数。
由于(|Z_k|)表示的是使(k)不变的置换个数，(D(a_j))表示的是置换(a_j)下不变的元素个数，二者显然可以建立一个等量关系：
然后，假设共有(N={1,2,...,n})中共有(L)个等价类（注意，(L)就是一般情况下要求的东西），即设(N=E_1+E_2+...+E_L)。
重新考虑(sum_{k=1}^n|Z_k|)，就可以发现：
根据最早的那个公式，(|E_k| imes |Z_k|=|G|)，得到：
简单移项得到：
(Polya)定理
考虑到在(Burnside)引理中的(D(a_j))依旧不好算。
定义一个置换(g_i)的循环个数为(c(g_i))。
容易发现，对于(g_i)同一循环节中的元素涂上相同颜色所得方案数(m^{c(g_i)})，就等于(a_i)作用下不变的图象数。
也就是说：
这就是(Polya)定理的公式了。
(Polya)定理模板题
题目链接：【洛谷4980】【模板】Polya定理。
考虑本质不同只需要判旋转，因此共有(n)种置换方式，其中第(i)种置换方式就是将所有数转(i)位。
显然，第(i)种置换中环的个数应该是(gcd(i,n))，因此得到答案的式子为：
看到(gcd)，自然而然想到莫比乌斯反演，按照它的经典套路，枚举(gcd)：
其中，后半部分的式子显然就是(phi(frac nd))，也就是：
因此，枚举(d)，然后暴力计算(phi(frac nd))，这道题就做完了。
参考文献
2001 - 符文杰：《Pólya原理及其应用》
(Postscript)
(Polya)定理感觉应该是一个很有用的计数工具，但它的题目也都很难，余还要多加研究。。。