[整理]Pólya 定理入门到入土

0.闲扯

请注意，Pólya 是匈牙利数学家，请尽量不要漏掉 ó 上的长音符写成 Polya （Polay 就更不行了）。

1.前置知识

参见《抽象代数 I》
为了照顾不了解的同学，我们从最基础的定义开始。

1.0 群论简介

已知一个集合 (G) 和定义在 (G) 上的运算 (circ)，说 (G) 是一个群当且仅当其满足：
((1)forall a,b,cin G, (acirc b)circ c=acirc (bcirc c))（结合律）
((2)exists e,) 使得 (forall ain G, ecirc a=acirc e=a)（单位元）也有的屑译者将其译作“幺元”
((3)forall ain G, exists bin G, acirc b=bcirc a=e)（逆元）
此时也将这个群记作 ((G,circ))。

若 ((G,circ)) 是群，(Hsubseteq G,H evarnothing) 且 (H) 对运算 (circ) 构成群，那么说 (H) 是 (G) 的子群，记作 (Hle G)。
设 (H,Kin G)，定义它们的积 (HK={hk|hin H,kin K})，(K={a}) 时也可记作 (Ha)。
若 (G) 是群，(Hle G, ain G)，则称 (aH) （同理，(Ha)）为 (H) 的一个左（同理，右）陪集。
易知左陪集和右陪集的个数相等，我们将其记作 (|G:H|)。
Lagrange 定理：若 (G) 为有限群，(Hle G)，则 (|G|=|G:H||H|)，证明显然，留作练习。
若 (G) 是群，(Min G)，称 (G) 的所有包含 (M) 的子群之交为由 (M) 生成的子群，记作 (langle M angle)。

设 (G) 为群，(S) 为集合，定义 (G) 在 (S) 上的一个作用为一个映射

[egin{aligned} varphi:G imes S& ightarrow S\ (g,s)&mapsto g(s) end{aligned} ]

满足 (e(s)=s, g_1(g_2(s))=(g_1g_2)(s))。其中 (e) 是 (G) 的单位元，(g_1,g_2in G,sin S)。
对于 (sin S)，我们定义它在 (G) 作用下的轨道 ( ext{Orb}(s)={g(s)|gin G})。
定义等价关系 (sim:forall s_1,s_2in S, s_1sim s_2Leftrightarrowexists gin G, g(s_1)=s_2)，容易验证 ( ext{Orb}(s)) 即为 (s) 的等价类。
对于 (sin S)，定义其稳定化子 ( ext{Stab}(s)={gin G|g(s)=s})。
容易发现，(| ext{Orb}(s)|=|G: ext{Stab}(s)|=|G|/| ext{Stab}(s)|)，证明留做练习。

1.1 置换与置换群

设 ([n]={1,2,dots ,n})，([n]) 到自身的一个双射称为 ([n]) 上的一个置换。
易证 ([n]) 上的全体 (n!) 个置换对映射复合构成群，称为 ([n]) 上的对称群或 (n) 级对称群，记作 (S_n)。对称群的子群称为置换群。
定义 ([n]) 上的二面体群 (D_n={sigma_i, au_j |i,j=1,2,dots ,n})，其中 (sigma_i(a)=a+ipmod n, au_j(a)=-a+jpmod n, ain[n])。
二面体群的子群 ({sigma_i |i=1,2,dots ,n}) 称作 ([n]) 上的循环群。

1.2 轮换与轮换指标

若置换 (sigma) 满足 (sigma(i_1)=i_2, sigma(i_2)=i_3,dots ,sigma(i_{k-1})=i_k, sigma(i_k)=i_1) 且 (forall j e i_1,i_2,dots ,i_k, sigma(j)=j)，那么称 (sigma) 是一个 (k)-轮换，记作 (sigma=(i_1i_2dots i_k))。
显然，任意非恒等置换都可唯一分解为不相交轮换的复合。
用 (l_i(sigma)) 表示 (sigma) 的分解中 (i)-轮换的个数，称 ((l_1(sigma),l_2(sigma),dots ,l_n(sigma))) 为 (sigma) 的轮换型号，记作 ( ext{type}(sigma))。
Cauchy 公式：(S_n) 中型号为 ((l_1,l_2,dots ,l_n)) 的置换个数为 (dfrac{n!}{l_1!l_2!dots l_n! 1^{l_1}2^{l_2}dots n^{l_n}})。
证明留作练习。
设 (G) 是一个 (n) 元置换群，定义 (G) 的轮换指标为关于变量 (x_1,x_2,dots ,x_n) 的一个多项式 (P_G(x_1,x_2,dots ,x_n)=dfrac{1}{|G|}sumlimits_{sigmain G}x_1^{l_1(sigma)}x_2^{l_2(sigma)}dots x_n^{l_n(sigma)})。
例：因为 (S_3={(1)(2)(3),(12)(3),(13)(2),(23)(1),(123),(132)})，所以 (P_{S_3}=dfrac{x_1^3+3x_1x_2+2x_3}{6})。
下面给出一个计算轮换指标的例子（绝大多数证明过程蒯了《组合数学》上的）：
设 (sigma=(12dots n))，求由 (sigma) 生成的 (n) 阶循环群 (langlesigma angle) 的轮换指标。
显然 (langlesigma angle={sigma,sigma^2,dots ,sigma^n})，下面我们需要计算 ( ext{type}(sigma^k))。
设 (1le kle n)，因为 (sigma) 为 (n)-轮换，所以 (gcd(k,n)=1) 时 (sigma^k) 也为 (n)-轮换，而 (k|n) 时 (sigma^k) 可分解为 (k) 个 (n/k)-轮换的复合。
对于更加一般的情况，可以设 (d=gcd(k,n))，此时 (sigma^k=(sigma^d)^{k/d})，易证它也是 (d) 个 (n/d)-轮换的复合。
由上即得 (l_i(sigma^k)=egin{cases}0,&i e n/d,\d,&i=n/d,end{cases})，
而 (P_{langlesigma angle}(x_1,x_2,dots ,x_n)=dfrac 1nsumlimits_{k=1}^n(x_{n/gcd(k,n)})^{gcd(k,n)})。
优化：这个式子求起来是 (O(n)) 的，一般无法使用，考虑计算重复的答案。
发现有些 (gcd) 是相同的，考虑计算 (1le kle n,gcd(k,n)=d) 的 (k) 的个数，同除以 (d) 就得到它等于 (varphi(n/d))。
所以原式等于 (dfrac 1nsumlimits_{d|n}varphi(n/d)(x_{n/d})^d)。

2.Pólya 定理

终于要进入正题了

2.0 Burnside 引理

设 (G) 作用在 (S) 上，(psi(g)={sin S|g(s)=s})，则 (G) 的轨道个数为 (dfrac{1}{|G|}sumlimits_{gin G}|psi(g)|)。
即 (G) 作用在 (S) 上的轨道个数等于 (G) 的不动点个数的平均值。

2.1 Pólya 定理

设 (A) 和 (C) 分别为 (n) 元集和 (m) 元集，记 (C^A={f|f:A ightarrow C})。
设 (G) 为 (A) 上置换群，(G) 作用在 (C^A) 上，则轨道个数为 (P_G(m,m,dots ,m))。
证明从略，因为作者也不会。

3.应用

定理的描述很简单，那么它如何应用呢？

3.0 例题

洛谷P4980 【模板】Pólya 定理
观察题目，发现实质上是一个循环群（设为 (G)）作用在颜色的 (n) 元集上，那么就可以直接套定理了：(ans=P_G(n,n,dots ,n)=dfrac 1nsumlimits_{d|n}varphi(n/d)n^d)。
此题数据范围较小，暴力求欧拉函数可以很宽松地卡过去。

const int p=1000000007;
int T,n;
il int Phi(int n){
  int res=n;
  for(rg int i=2;i*i<=n;i++){
    if(n%i==0){
      res-=res/i;
      while(n%i==0)n/=i;
    }
  }
  return n>1?res-res/n:res;
}
il int Pow(int a,int b){
  int res=1;
  while(b){
    if(b&1)res=1ll*res*a%p;
    a=1ll*a*a%p,b>>=1;
  }
  return res;
}
int main(){
  Read(T);
  while(T--){
    Read(n);
    int res=0,d;
    for(d=1;d*d<n;d++){
      if(n%d==0){
        res=(res+1ll*Phi(n/d)*Pow(n,d)%p)%p;
        res=(res+1ll*Phi(d)*Pow(n,n/d)%p)%p;
      }
    }
    if(d*d==n)res=(res+1ll*Phi(n/d)*Pow(n,d)%p)%p;
    res=1ll*res*Pow(n,p-2)%p;
    cout<<res<<endl;
  }
  return 0;
}

4.拓展

4.0 带权的 Burnside 引理和 Pólya 定理

给每条轨道加一个权值 (w( ext{Orb}(s)))，定理的形式也有了变化。
Burnside 引理中的 (|psi(g)|) 替换成内部元素的权值之和；Pólya 定理中的 (P_G(m,m,dots ,m)) 替换成 (P_G(sumlimits_{cin C}w(c),sumlimits_{cin C}w(c)^2,dots ,sumlimits_{cin C}w(c)^n))。

4.1 思考

由于时间原因不再多讲（作者懒），这里留下几个问题供大家思考。
1.仿照循环群，计算二面体群的轮换指标。
2.尝试求 (n) 阶简单图的个数。
3.洛谷P4128 [SHOI2006]有色图。有色图？来了来了，在哪里啊！

5.参考文献

([1]) 赵春来, 徐明耀. 抽象代数 I. 北京：北京大学出版社, 2008.
([2]) 冯荣权, 宋春伟. 组合数学. 北京：北京大学出版社, 2015.