也许更好的阅读体验

$Burnside引理$Burnside引理

• 公式
  $\begin{array}{c}{\displaystyle L=\frac{1}{\mid G\mid }\sum _{i=1}^{\mid G\mid }{D}_{G_i}}\end{array}$L=∣G∣1​i=1∑∣G∣​DGi​​​

• 一些定义
  $E_i$Ei​ 表示与 $i$i同类的方案
  $Z_i$Zi​ 表示使 $i$i不变的置换
  $G$G 表示所有的置换方法
  $D_i$Di​ 表示 $i$i这种置换能使多少方案不变
  $n$n 表示方案总数
  $L$L 表示本质不同的方案数

• 引理的引理
  $\mid E_i\mid \ast \mid Z_i\mid =\mid G\mid$∣Ei​∣∗∣Zi​∣=∣G∣ $//$                          //这个我不会证明
  $\begin{array}{c}{\displaystyle n=\sum _{i=1}^L\mid E_i\mid }\end{array}$n=i=1∑L​∣Ei​∣​ $//$                                  //这个就是按照定义，注意的是 $E_i$Ei​表示的是本质不同的第 $i$i种方案
  $\begin{array}{c}{\displaystyle \sum _{i=1}^n\mid Z_i\mid =\sum _{i=1}^{\mid G\mid }{D}_{G_i}}\end{array}$i=1∑n​∣Zi​∣=i=1∑∣G∣​DGi​​​ $//$                      //这个也是按照定义，就是换了个计算方法，计算的是同样的东西

• Burnside引理
  $\begin{array}{c}{\displaystyle \sum _{j=1}^n\mid Z_j\mid =\sum _{i=1}^L\sum _{j\in E_i}\mid Z_j\mid =\sum _{i=1}^L\mid E_i\mid \cdot \mid Z_i\mid =L\cdot \mid G\mid }\end{array}$j=1∑n​∣Zj​∣=i=1∑L​j∈Ei​∑​∣Zj​∣=i=1∑L​∣Ei​∣⋅∣Zi​∣=L⋅∣G∣​
  $\begin{array}{c}{\displaystyle \therefore L\cdot \mid G\mid =\sum _{j=1}^{\mid G\mid }{D}_{G_i}}\end{array}$∴L⋅∣G∣=j=1∑∣G∣​DGi​​​
  $\begin{array}{c}{\displaystyle \therefore L=\frac{1}{\mid G\mid }\sum _{i=1}^{\mid G\mid }{D}_{G_i}}\end{array}$∴L=∣G∣1​i=1∑∣G∣​DGi​​​

$Polya定理$Polya定理

• 公式
  $\begin{array}{c}{\displaystyle L=\frac{1}{\mid G\mid }\sum _{i=1}^{\mid G\mid }{m}^{C_{G_i}}}\end{array}$L=∣G∣1​i=1∑∣G∣​mCGi​​​
  其中 $m$m为颜色个数, $C_i$Ci​为第 $i$i种置换有多少个循环

$一个置换的循环个数$一个置换的循环个数

一个项链有 $n$n个珠子,用 $k$k种颜色涂染会形成多少种不同的项链
两条可通过旋转得到的项链为相同项链

有 $n$n种置换方式 $($(每次旋转 $0,1,\mathrm{2...}n$0,1,2...n个珠子 $)$)
对于一次旋转 $i$i个珠子的方式，有 $gcd(i,n)$gcd(i,n)个循环
证明
每个循环有的珠子的个数应是一样的
假设从 $x$x号珠子开始置换，循环结束时一定回到 $x$x号珠子 如 $x-\>(x+i-1)\%n+1-\>(x+2i-1)\%n+1-\>x$x−>(x+i−1)%n+1−>(x+2i−1)%n+1−>x
假设循环有 $p$p个珠子，那么循环 $p$p次就回到原来的珠子，此时转过 $i$i和 $n$n的最小公倍数个珠子
$p\cdot i=i\cdot n/gcd(i,n)k\in Z$p⋅i=i⋅n/gcd(i,n)   k∈Z
$\therefore p=n/gcd(i,n)$∴p=n/gcd(i,n)
每个循环有 $p$p个珠子那么就有 $n/p=gcd(i,n)$n/p=gcd(i,n)个循环