Burnside定理及polya定理小记

· · 个人记录

例题

Burnside定理：

定义：

|X/G|=\frac{1}{|G|}=\sum_{g\in G}|X^g|

设 A 和 B 为有限集合，

$X$： 表示为一些从 $A$ 到 $B$ 的映射组成的集合 $G$： 表示在 $A$ 上的置换群，且 $X$ 中的映射在 $G$ 中置换作用下封闭 $X/G$： 表示 $G$ 作用下在 $X$ 上产生的等价类的集合（即若 $X$ 中的两个映射经过 $G$ 中的置换作用后相等，则它们在同一等价类中）。 $X^g$：表示在置换 $g$ 的作用下，$X$ 不变的元素的集合，即 $X^g=\{x|x\in X,g(x)=x\}

举例：

不妨拿例题来举例，当 n=3 时

显然

$B$ 表示三个颜色的集合 $X/G=\{(1,1,1),(1,1,2),(1,1,3),(1,2,2),(1,2,3),(1,3,3),(2,2,2),(2,2,3),(2,3,3),(3,3,3),(1,3,2)\}$，即 $|X/G|=11 G=\{\dbinom{a_1,a_2,a_3}{a_1,a_2,a_3},\dbinom{a_1,a_2,a_3}{a_2,a_3,a_1},\dbinom{a_1,a_2,a_3}{a_3,a_1,a_2}\}$，即 $|G|=3

对于 g=\dbinom{a_1,a_2,a_3}{a_1,a_2,a_3}，显然 |X^g|=3^3=27

对于 g=\dbinom{a_1,a_2,a_3}{a_2,a_3,a_1}，显然 X^g=\{(1,1,1),(2,2,2),(3,3,3)\}，即 |X^g|=3

对于 g=\dbinom{a_1,a_2,a_3}{a_3,a_1,a_2}，显然 X^g=\{(1,1,1),(2,2,2),(3,3,3)\}，即 |X^g|=3

显然等式左边等于等式右边

证明：

考虑引入轨道稳定子定理：G 和 X 定义同上，定义 g(x) 为元素 x 在置换 g 下变成的元素，定义 \forall x\in X,G^x=\{g|g(x)=x,g\in G\},G(x)=\{g(x)|g\in G\}，其中 G^x 称为 x 的稳定子，G(x) 称为 x 的轨道，则有：

|G|=|G^x||G(x)|

考虑证明该定理：

首先可以证明 G^x 是 G 的子群，因为

封闭性：f,g\in G^x有 f\circ g(x)=f(g(x))=f(x)=x，，所以 f\circ g\in G^x

结合律：显然置换的乘法满足结合律

单位元：因为 I(x)=x，所以 I\in G^x

逆元：若 g\in G^x，则 g^{-1}(x)=g^{-1}(g(x))=g^{-1}\circ g(x)=I(x)=x，所以 g^{-1}\in G^x

而 G^x\in G，所以 G^x 是 G 的子群

而根据群论中拉格朗日定理，可得：

|G|=|G^x|[G:G^x]

其中 [G:G^x] 为 G^x 不同的左陪集个数。接下来只需证明 |G(x)|=[G:G^x]，我们将其转化为证明存在一个从 G(x) 到 G^x 所有不同左陪集的双射。令 \varphi(g(x))=gG^x，下证 \varphi 为双射

若 g(x)=f(x)，两边同时左乘 f^{-1}，可得 f^{-1}\circ g(x)=I(x)=x，所以 f^{-1}\circ g\in G^x，由陪集的性质可得 (f^{-1}\circ g)G^x=G^x，即 gG^x=fG^x

反过来可证，若 gG^x=fG^x，则有 g(x)=f(x)

以上两点说明对于一个 g(x)，只有一个左陪集与其对应，即 \varphi 是一个从 G(x) 到左陪集的映射

又显然 \varphi 有逆映射，因此 \varphi 是一个双射

然后就可以开始证明了：

\sum_{g\in G}|X^g|&=|\{(g,x)|(g,x)\in G\times X,g(x)=x\}|\\ &=\sum_{x\in X}|G^x|\\ &=\sum_{x\in X}\frac{|G|}{|G(x)|}\quad\quad\quad\\ &=|G|\sum_{x\in X}\frac{1}{|G(x)|}\\ &=|G|\sum_{Y\in X/G}\sum_{x\in Y}\frac{1}{|G(x)|}\\ &=|G|\sum_{Y\in X/G}\sum_{x\in Y}\frac{1}{|Y|}\\ &=|G|\sum_{Y\in X/G}1\\ &=|G||X/G| \end{aligned}

证毕。

Polya定理

在于 Burnside 引理相同的前置条件下，内容修改为：

|X/G|=\frac{1}{|G|}\sum_{g\in G}|B|^{c(g)}

其中 c(g) 表示置换 g 最多能拆分成的不相交的循环置换的数量。

证明：

显然就是要证明 \forall |X^g|=|B|^{c(g)}，考虑 g(x)=x 的条件，即对于每个不相交的循环置换中的元素映射到 B 中的同一元素，所以 |X^g|=|B|^{c(g)}

最后再用一条连等式来总结：

|X/G|=\frac{1}{|G|}\sum_{g\in G}|B|^{c(g)}=\sum_{g\in G}\frac{|X^g|}{|G|}=\sum_{x\in X}\frac{|G^x|}{|G|}=\sum_{x\in X}\frac{1}{|G(x)|}

而对于 \sum\limits_{x\in X}\frac{1}{|G(x)|}，我们理解为当 x 有 |G(x)| 个等价类时，它的贡献是 \frac{1}{|G(x)|}，即当所有的等价类贡献加起来，就恰好在 |X/G| 中有 1 的贡献。

例题解析：

显然可以根据 c(g) 的不同的值来计算答案，而 c(g) 在题目中的实际意义就是 gcd(k,n)，而 k 表示项链右旋 k 位。

剩下显然就是欧拉函数和快速幂，这里不多赘述，上代码：

#include<bits/stdc++.h>
#define int long long
using namespace std;
const int mod=1e9+7;
int T,n,ans;
int ksm(int ds,int zs)
{
    int re=1;
    while(zs)
    {
        if(zs&1) re=re*ds%mod;
        ds=ds*ds%mod;
        zs=zs/2;
    }
    return re;
}
int get_phi(int x)
{
    int re=x;
    for(int i=2;i*i<=x;i++)
    {
        if(x%i==0)
        {
            re=re-re/i;
            while(x%i==0) x=x/i;
        }
    }
    if(x!=1) re=re-re/x;
    return re;
}
signed main()
{
    scanf("%lld",&T);
    while(T--)
    {
        ans=0;
        scanf("%lld",&n);
        for(int i=1;i*i<=n;i++)
        {
            if(n%i==0)
            {
                ans=(ans+get_phi(i)*ksm(n,n/i)%mod)%mod;
                if(i*i!=n) ans=(ans+get_phi(n/i)*ksm(n,i)%mod)%mod;
            }
        }
        ans=ans*ksm(n,mod-2)%mod;
        printf("%lld\n",ans);
    }
    return 0;
}

例题1.2

因为每种颜色使用有限制，所以显然不能直接使用 polya 定理，而相比 polya，更好是使用 Burnside 定理。

考虑对于一个置换操作 g，有哪些 x\in X 是不变的，考虑将 g 分解乘不相交的置换集，对于每个置换集显然颜色要相同，考虑 dp，用 f_{i,j,k} 表示使用 i 个 red，j 个 blue，k 个 green 的方案数，假设新加入的交换集有 t 个元素，那么显然它可以三个颜色中的一种，所以 f_{i,j,k}=f_{i-t,j,k}+f_{i,j-t,k}+f_{i,j,k-t}

而将每个 |X^g| 加起来就好了，注意还要计算不动的交换集，最后是除以m+1。

上代码：

#include<bits/stdc++.h>
using namespace std;
int sr,sb,sg,n,m,p,ans,inv;
int f[22][22][22];
int a[100],c[100],idx;
bool vis[100];
int ksm(int ds,int zs)
{
    int re=1;
    while(zs)
    {
        if(zs&1) re=re*ds%p;
        ds=ds*ds%p;
        zs=zs/2;
    }
    return re;
}
void dfs(int wz)
{
    vis[wz]=true;
    c[idx]++;
    if(!vis[a[wz]]) dfs(a[wz]);
}
void calc()
{
    memset(f,0,sizeof f);
    f[0][0][0]=1;
    for(int i=1;i<=idx;i++)
    {
        for(int re=sr;re>=0;re--)
        for(int bl=sb;bl>=0;bl--)
        for(int gr=sg;gr>=0;gr--)
        {
            f[re][bl][gr]=0;
            if(re>=c[i]) (f[re][bl][gr]+=f[re-c[i]][bl][gr])%=p;
            if(bl>=c[i]) (f[re][bl][gr]+=f[re][bl-c[i]][gr])%=p;
            if(gr>=c[i]) (f[re][bl][gr]+=f[re][bl][gr-c[i]])%=p;
        }
    }
    (ans+=f[sr][sb][sg])%=p;
}
int main()
{
    scanf("%d %d %d %d %d",&sr,&sb,&sg,&m,&p);
    n=sr+sb+sg,inv=ksm(m+1,p-2);
    idx=0;
    for(int i=1;i<=n;i++)
        a[i]=i,vis[i]=false;
    for(int i=1;i<=n;i++) if(!vis[i]) idx++,dfs(i);
    calc();
    while(m--)
    {
        idx=0;
        for(int i=1;i<=n;i++)
            scanf("%d",&a[i]),vis[i]=false;
        for(int i=1;i<=n;i++) if(!vis[i]) idx++,c[idx]=0,dfs(i);
        calc();
    }
    printf("%d\n",ans*inv%p);
    return 0;
}