声明：本知识点为帮助大家更好地理解置换群论这一抽象的内容，一些定义中掺杂了撰写者自身的理解，和严格的数学定义有些出入，基本为数学定义的缩小解释和限制解释。
另外，统一一些符号的使用。
对集合A，|A|表示A中元素的个数
对命题p，若为真，则[p]=1；若为假，则[p]=0。如[1>2]=0，[gcd(3,5)=1]=1
对一个群，e表示该群的单位元， g − 1 g^{-1} g−1表示群中元素 g g g的逆元
问题描述
一个n个点的环，用n种颜色去染。求有多少种本质不同的染色方案。
两种染色方案相同当且仅当通过旋转（不包括翻转）后，每个点的颜色都相同。
解决方案
为了让大家看起来有耐心，我先把结论放出来。事实上，本题的答案是 1 n ∑ i = 1 n n g c d ( i , n ) \frac 1n \sum^n_{i=1} n^{gcd(i,n)} n1∑i=1nngcd(i,n)
但是，想要证明这个结果着实要下一点功夫。事实上，要得到这个答案，需要使用Burnside引理。那么，Burnside引理在说什么呢？
Burnside引理内容
这个引理的内容并不是很通俗易懂，需要先给出一些定义才能表述清楚
定义1（置换）
n元集合A到它自身的一个一一映射，称为A上的一个n元置换或n阶置换。简记为
σ
=
(
1
2
…
n
i
1
i
2
…
i
n
)
\mathbf{\sigma} = \left( \begin{array}{cccc} 1 & 2 & \ldots & n\\ i_1 & i_2 & \ldots & i_n\\ \end{array} \right)
σ=(1i12i2……nin)
其中，
i
1
,
i
2
,
…
,
i
n
i_1,i_2,\ldots ,i_n
i1,i2,…,in为1到n的排列
意思是，把第
i
1
i_1
i1个点换到1号位置，第
i
2
i_2
i2个点换到2号位置，……，第
i
n
i_n
in个点换到n号位置。这个记录方法被称为“两行法”（我自己命名的）。
因为第一行通常为按顺序的1-n，所以经常省略第一行，用
(
i
1
,
i
2
,
.
.
.
,
i
n
)
(i_1,i_2,...,i_n)
(i1,i2,...,in)表示一个n元置换。这个表示方法被称为“一行法”。
定义2（同种染色置换，同种染色置换群）
我们把对应同一种染色方案的置换称为同种染色置换。全部同种染色置换构成一个集合 G = { g 1 , g 2 , . . . , g n } G=\{g_1,g_2,...,g_n\} G={g1,g2,...,gn}。本题中，G包含s=n个元素，分别表示顺势针转0~n-1次。定义G上的二元运算*，对 ∀ i , j \forall i,j ∀i,j， g i ∗ g j g_i*g_j gi∗gj表示先按 g i g_i gi置换，再按 g j g_j gj置换。可以证明（参考结论1）， ( G , ∗ ) (G,*) (G,∗)构成一个群，这称为同种染色置换群。
定义3（朴素染色方案）
即不考虑旋转情况的染色方案。本问题* N = n n N=n^n N=nn种朴素染色方案。如无特别说明，此后中的染色方案都指朴素染色方案。可以建立一个正整数到染色方案的一一映射，即可以用一个1~N的正整数表示一种染色方案。
定义4（同种染色置换对朴素染色方案的作用）
对一种同种染色置换 g （ g ∈ G ） g（g\in G） g（g∈G）和每一种染色方案k（ 1 ≤ k ≤ N 1\le k\le N 1≤k≤N），g(k)也是一个1~N的整数,表示另一种染色方案，即将染色方案k按照g进行置换。从k到g(k)的映射称为g对k的作用。特别注意，g(k)可能等于k（如k表示将所有点染成红色，则无论怎么旋转，显然染色方案不变），也可能不等于k。但无论g(k)与k是否相等，g(k)与k都是本质相同的染色（因为是同种染色置换得到的，在最终答案中只考虑一次）。
介绍了这么多，终于可以阐述Burnside引理的内容了。首先，构造一个函数 ∀ g ∈ G ， x ∈ { 1 , 2 , . . . , N } ， f ( g , x ) = [ g ( x ) = x ] \forall g\in G，x\in \{1,2,...,N\}，f(g,x)=[g(x)=x] ∀g∈G，x∈{1,2,...,N}，f(g,x)=[g(x)=x]。这是一个典型的用于计数的函数。设 h ( g i ) = ∑ k = 1 N f ( g i , k ) h(g_i)=\sum^N_{k=1}f(g_i,k) h(gi)=∑k=1Nf(gi,k)，即满足 g i ( k ) = k g_i(k)=k gi(k)=k的染色方案个数。那么最终答案 a n s = 1 s ∑ i = 1 s h ( g i ) ans=\frac 1s\sum^s_{i=1}h(g_i) ans=s1∑i=1sh(gi)，其中 s = ∣ G ∣ s=|G| s=∣G∣
Burnside引理证明
结论1
(G,*)构成一个群。
根据群的定义，满足封闭性，结合律，单位元，逆元四条性质的集合和二元运算构成群（四条性质具体内容不了解的可以百度）。
显然，G对*运算满足封闭性，结合律。单位元e即旋转0次对应的置换。除e以外，旋转i次置换的逆元为旋转n-i次置换。
事实上，这是Burnside引理基本的适用范围。也就是说，只有同种染色置换能构成群的问题，才能使用Burnside引理来解决。
定义5（不动点集）
对于任意染色方案k，G中一定存在一些元素满足g(k)=k（至少e一定满足要求，因此“一定”的表述的严谨的）。设所有满足g(k)=k的同种染色置换构成k的不动点集，用 Z k Z_k Zk表示。可以证明， ( Z k , ∗ ) (Z_k,*) (Zk,∗)构成一个群（结合律，单位元显然，封闭性，逆元也易证）。
定义6（等价类）
对将G中的s个元素分别作用于k，得到k的等价类，用符号 E k E_k Ek表示。 E k = { g 1 ( k ) , g 2 ( k ) , . . . , g s ( k ) } E_k=\{g_1(k),g_2(k),...,g_s(k)\} Ek={g1(k),g2(k),...,gs(k)}包含全部本质上和k相同的朴素染色方案。特别注意， g 1 ( k ) , g 2 ( k ) , . . . , g s ( k ) g_1(k),g_2(k),...,g_s(k) g1(k),g2(k),...,gs(k)中存在一些相同的数，应当剔除重复的结果，得到 E k E_k Ek。
设 E = { k 1 , k 2 , . . . , k m } E=\{k_1,k_2,...,k_m\} E={k1,k2,...,km}，显然有 E = E k 1 = E k 2 = . . . = E k m E=E_{k_1}=E_{k_2}=...=E_{k_m} E=Ek1=Ek2=...=Ekm
我们最终要计算有多少种本质不同的染色方案，其实就是要计算一共有多少个等价类。
结论2
对1~N中的任何一个数k，有 ∣ G ∣ = ∣ E k ∣ ⋅ ∣ Z k ∣ |G|=|E_k|\cdot |Z_k| ∣G∣=∣Ek∣⋅∣Zk∣
设 Z k = { g i 1 , g i 2 , . . . , g i p } , E k = { g j 1 ( k ) , g j 2 ( k ) , . . . , g j q ( k ) } Z_k=\{g_{i_1},g_{i_2},...,g_{i_p}\},E_k=\{g_{j_1}(k),g_{j_2}(k),...,g_{j_q}(k)\} Zk={gi1,gi2,...,gip},Ek={gj1(k),gj2(k),...,gjq(k)}
设 H = { g ∣ g = g i x ∗ g j y , 1 ≤ x ≤ p , 1 ≤ y ≤ q } H=\{g|g=g_{i_x}*g_{j_y},1\le x \le p,1\le y \le q\} H={g∣g=gix∗gjy,1≤x≤p,1≤y≤q}。若y不相等，则 g ( k ) = g j y ( g i x ( k ) ) = g j y ( k ) g(k)=g_{j_y}(g_{i_x}(k))=g_{j_y}(k) g(k)=gjy(gix(k))=gjy(k)不相等。若y相等且x不相等，则 g ∗ g j y − 1 = g i x g*g_{j_y}^{-1}=g_{i_x} g∗gjy−1=gix不相等。因此有H中任意两个元素都不相同，H*有 p q pq pq个元素。
显然有 H ⊆ G H\subseteq G H⊆G，下证 G ⊆ H G\subseteq H G⊆H。
对G中任意元素g,有 g ( k ) ∈ E k g(k)\in E_k g(k)∈Ek，设 g ( k ) = g j y ( k ) g(k)=g_{j_y}(k) g(k)=gjy(k)。则有 g j y − 1 ( g ( k ) ) = k g_{j_y}^{-1}(g(k))=k gjy−1(g(k))=k，即 g ∗ g j y − 1 ∈ Z k g*g_{j_y}^{-1}\in Z_k g∗gjy−1∈Zk。则有 g i x = g ∗ g j y − 1 g_{i_x}=g*g_{j_y}^{-1} gix=g∗gjy−1， g = g i x ∗ g j y ∈ H g=g_{i_x}*g_{j_y}\in H g=gix∗gjy∈H。所以 G ⊆ H G\subseteq H G⊆H。
所以有 G = H G=H G=H。
因为 ∣ H ∣ = p q = ∣ E k ∣ ⋅ ∣ Z k ∣ |H|=pq=|E_k|\cdot |Z_k| ∣H∣=pq=∣Ek∣⋅∣Zk∣，所以 ∣ G ∣ = ∣ E k ∣ ⋅ ∣ Z k ∣ |G|=|E_k|\cdot |Z_k| ∣G∣=∣Ek∣⋅∣Zk∣
这个结论证明了，对一个等价类 E = { k 1 , k 2 , . . . , k m } E=\{k_1,k_2,...,k_m\} E={k1,k2,...,km}，有 ∑ i = 1 m ∣ Z k i ∣ = ∣ G ∣ \sum^m_{i=1}|Z_{k_i}|=|G| ∑i=1m∣Zki∣=∣G∣
结论3（Burnside引理）
f ( g , x ) f(g,x) f(g,x)和 h ( g i ) h(g_i) h(gi)的定义见Burnside引理。接下来将开启一波愉快的推式子。
∑ i = 1 s h ( g i ) = ∑ i = 1 s ∑ x = 1 N f ( g i , x ) = ∑ x = 1 N ∑ i = 1 s f ( g i , x ) = ∑ x = 1 N ∣ Z x ∣ \sum^s_{i=1}h(g_i)=\sum^s_{i=1}\sum^N_{x=1}f(g_i,x)=\sum^N_{x=1}\sum^s_{i=1}f(g_i,x)=\sum^N_{x=1}|Z_x| ∑i=1sh(gi)=∑i=1s∑x=1Nf(gi,x)=∑x=1N∑i=1sf(gi,x)=∑x=1N∣Zx∣
这道题求的答案 a n s ans ans是等价类个数。
由结论2， ∑ x = 1 N ∣ Z x ∣ = a n s ⋅ ∣ G ∣ \sum^N_{x=1}|Z_x|=ans\cdot |G| ∑x=1N∣Zx∣=ans⋅∣G∣。所以 a n s = 1 s ∑ i = 1 s h ( g i ) ans=\frac 1s\sum^s_{i=1}h(g_i) ans=s1∑i=1sh(gi)，其中 s = ∣ G ∣ s=|G| s=∣G∣
问题最终解决
希望大家没有忘记原先的问题。如果忘了，可以回到最上面看一下。
在这个问题当中，我们最重要的就是求出 c ( g i ) c(g_i) c(gi)。我们不妨先从简单的情况想起。我们设 g i g_i gi表示顺势针转i次的置换。显然有， c ( g 0 ) = N = n n c(g_0)=N=n^n c(g0)=N=nn，也就是说，对 ∀ k , g 0 ( k ) = k \forall k,g_0(k)=k ∀k,g0(k)=k。
同样的，显然有 c ( g 1 ) = n c(g_1)=n c(g1)=n，只有所有点颜色都相同的朴素染色方案，才有顺势针旋转1次后，结果不变。
对于旋转i次，要求第1个点，第1+i个点，第1+2i个点,…,第ki%n+1个点颜色必须相同。所有形如(ki+1)%n+1的点颜色必须相同；形如(ki+2)%n+1的点必须相同…由裴蜀定理一共有 g c d ( n , i ) gcd(n,i) gcd(n,i)组点，每组点的颜色必须相同。因此， c ( g i ) = n g c d ( n , i ) c(g_i)=n^{gcd(n,i)} c(gi)=ngcd(n,i)
所以，这个问题的答案 a n s = 1 n ∑ i = 1 n n g c d ( n , i ) ans=\frac1n \sum^n_{i=1} n^{gcd(n,i)} ans=n1∑i=1nngcd(n,i)
Burnside引理升级版——Polya定理
所谓升级版，其实是Burnside引理的简化版。学习Polya定理之前要先了解另一种置换的表示法。
定义7（循环）
形如 5 → 1 → 2 → 3 → 4 → 5 5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5 5→1→2→3→4→5的（首尾相同，中间无重复）链，称为一个循环。这个循环表示将5换到1的位置、1换到2的位置、2换到3的位置、3换到4的位置、4换到5的位置，记作 ( 5 , 1 , 2 , 3 , 4 ) (5,1,2,3,4) (5,1,2,3,4)，称为5元循环。
一个循环中所包含的数，称为这个循环的元素。
定义8（“循环法”表示）
对于一个置换，除了用“两行法”，“一行法”表示，还有一种“循环法”。“循环法”描述一个置换所包含的全部循环。比如“一行法”表示的置换 ( 5 , 1 , 2 , 3 , 4 ) (5,1,2,3,4) (5,1,2,3,4)，包含一个循环 5 → 1 → 2 → 3 → 4 → 5 5\rightarrow 1\rightarrow 2\rightarrow 3\rightarrow 4\rightarrow 5 5→1→2→3→4→5，可以用一个括号，里面描述这个循环。“一行法”表示的 ( 5 , 1 , 2 , 3 , 4 ) (5,1,2,3,4) (5,1,2,3,4)用“循环法”表示仍是 ( 5 , 1 , 2 , 3 , 4 ) (5,1,2,3,4) (5,1,2,3,4)。再比如 ( 5 , 3 , 2 , 1 , 4 ) (5,3,2,1,4) (5,3,2,1,4)，包含 5 → 1 → 4 → 5 5\rightarrow 1\rightarrow 4\rightarrow 5 5→1→4→5和 3 → 2 → 3 3\rightarrow 2\rightarrow 3 3→2→3，这两个循环。因此， ( 5 , 3 , 2 , 1 , 4 ) 用 “ 循 环 法 ” 可 以 记 作 ( 5 , 1 , 4 ) ( 3 , 2 ) (5,3,2,1,4)用“循环法”可以记作(5,1,4)(3,2) (5,3,2,1,4)用“循环法”可以记作(5,1,4)(3,2)。
值得注意的是，仅改变括号顺序，并不改变置换。如 ( 1 , 2 ) ( 3 , 4 ) ( 5 ) (1,2)(3,4)(5) (1,2)(3,4)(5)和 ( 3 , 4 ) ( 5 ) ( 1 , 2 ) (3,4)(5)(1,2) (3,4)(5)(1,2)均表示 ( 2 , 1 , 4 , 3 , 5 ) (2,1,4,3,5) (2,1,4,3,5)。每个括号内数字的轮换也不改变置换，如“循环法”表示的 ( 5 , 1 , 2 , 3 , 4 ) ， ( 2 , 3 , 4 , 5 , 1 ) ， ( 1 , 2 , 3 , 4 , 5 ) (5,1,2,3,4)，(2,3,4,5,1)，(1,2,3,4,5) (5,1,2,3,4)，(2,3,4,5,1)，(1,2,3,4,5)均表示“一行法”下的 ( 5 , 1 , 2 , 3 , 4 ) (5,1,2,3,4) (5,1,2,3,4)。但交换一个括号内的两个数，可能会改变置换。如 ( 5 , 1 , 4 ) ( 3 , 2 ) (5,1,4)(3,2) (5,1,4)(3,2)表示 ( 5 , 3 , 2 , 1 , 4 ) (5,3,2,1,4) (5,3,2,1,4)，而 ( 1 , 5 , 4 ) ( 3 , 2 ) (1,5,4)(3,2) (1,5,4)(3,2)表示 ( 4 , 3 , 2 , 5 , 1 ) (4,3,2,5,1) (4,3,2,5,1)。
可以证明，任何一个置换均可用“循环法”唯一地表示。这里的唯一是指，每个循环都确定。
定义9（循环数）
一个置换所包含的循环的个数，为该置换的循环数。如 ( 1 , 2 ) ( 3 , 4 ) ( 5 ) (1,2)(3,4)(5) (1,2)(3,4)(5)的循环数为3， ( 1 , 5 , 4 ) ( 3 , 2 ) (1,5,4)(3,2) (1,5,4)(3,2)的循环数为2， ( 5 , 1 , 2 , 3 , 4 ) (5,1,2,3,4) (5,1,2,3,4)的循环数为1
对于任意置换g，设c(g)表示其循环数。
结论4
假设所求问题为n个点染m种颜色。对于任意置换 g i g_i gi，有 h ( g i ) = m c ( g i ) h(g_i)=m^{c(g_i)} h(gi)=mc(gi)，其中 h ( g i ) h(g_i) h(gi)为置换 g i g_i gi的不动点数， c ( g i ) c(g_i) c(gi)为置换 g i g_i gi的循环数。
对任意染色方案k， g i ( k ) = k g_i(k)=k gi(k)=k当且仅当 g i g_i gi的每个循环中所有元素颜色均相同。如k满足 g i = ( 1 , 5 , 4 ) ( 3 , 2 ) g_i=(1,5,4)(3,2) gi=(1,5,4)(3,2)， g i ( k ) = k g_i(k)=k gi(k)=k当且仅当第1,4,5个点颜色相同，第2,3个点颜色相同。因此有 h ( g i ) = m c ( g i ) h(g_i)=m^{c(g_i)} h(gi)=mc(gi)
结论5（Polya定理）
将结论4带入Burnside引理，得 a n s = 1 s ∑ i = 1 s h ( g i ) = 1 s ∑ i = 1 s m c ( g i ) ans=\frac 1s\sum^s_{i=1}h(g_i)=\frac 1s\sum^s_{i=1}m^{c(g_i)} ans=s1∑i=1sh(gi)=s1∑i=1smc(gi)