锐客网

  1. 首页 > it技术 > >

学习笔记|Burnside引理和polay计数学习笔记

学习笔记Burnsidepolay

首先提出一个问题，在一个2*2的矩阵里染色，旋转后相同算作一种，问有多少种染色方法。
【学习笔记|Burnside引理和polay计数学习笔记】学习笔记|Burnside引理和polay计数学习笔记
文章图片

显然穷举有那么多种，然后发现，（3，4，5，6）是同一种，（7，8，9，10）是一种，（11，12）是一种，（13，14，15，16），1是一种，2是一种。
发现，颜色少的时候，格子少的时候还是很容易枚举的，但是当问题规模大的时候，计算起来就会比较麻烦。
所以我们要来介绍一下Burnside定理和polay计数。
首先是Burnside定理，介绍之前，首先介绍几个概念。
一。置换群 G ，即所有的置换。以上面的为例子，置换一共有4种—旋转0度，旋转90度，旋转180度，旋转270度。所以 |G|=4
二。第二个概念， Zk对于每个元素K，这里的K满足 1<=k<=16 , G 中使得K保持不变的置换全体。
eg. Z1={g1,g2,g3,g4}
Z11={g1,g3}
三。第三个概念， Ek对于每个元素k，在四种置换下依次得到G下的转换的编号。
eg. E1={1} , E2={3,4,5,6}
没一个 Ei 其实就是一个等价类。
根绝上述定义，很容易得到一个公式： |Ek|?|Zk|=|G|
PS: |Ek| 是第k个元素，在四种变换下能形成的种数。
|Zk| k在|G|种置换下保持不变的个数。
G 表示置换种数
四。接着我们引出第四个概念。 D(gi) 表示在第i种置换下，没发生变换的元素个数
D(g1)=16,D(g2)=2,D(g3)=4,D(g4)=2
举例说就是在第一种置换下，16个元素都不会发生变化，在第二种置换下，1和2元素不会发生变化。
显然有个公式 ∑16j=1|Zj|=∑4i=1D(gi)
那么我们下面来进行最后的公式推导。
n=∑Li=1|Ei|ps.L个等价类
∑nj=1|Zj|=∑Li=1∑j∈E|Zj|=∑Li=1|Ei|?|Zi|=L?|G| 又因为 ∑16j=1|Zj|=∑4i=1D(gi) 所以推出了我们著名的Burnside定理：
L=1|G|?∑i=1|G|D(gi)
这就是著名的Burnside定理。 第一步求出所有的置换。第二步求出所有置换下，不变元素个数。所最开始的例子。ans=(16+2+4+2)/4=6.但是我们发现这个的第二部比较难求。所以我们接下来介绍polay计数法。
polay定理 首先先介绍一个概念—循环节。
观看下一组置换 (1,2,3,4,5)?>(3,5,1,4,2)
他的循环节是 (13)(25)(4) ,所以循环节长度是3，两个循环节是不想交的。
记上个问题按逆时针将四个格子放上1，2，3，4。
然后 G={g1,g2,g3,g4},|G|=4,g_i 的循环节个数记为c，则有下述情况
g1旋转0度： g1=(1)(2)(3)(4)c(g1)=4
g2旋转90度： g2=(4321)c(g2)=1
g3旋转180度： g3=(13)(24)c(g3)=2
g4旋转270度： g4=(1234)c(g4)=1
我们发现， gi 的同一个置换节中的元素用同一种颜色（现在可以用m种颜色，最初的样例是m=2）则染色得到的方案数 mc[i]就是在上面 gi置换下不变的元素个数
2c(g1)=24=16=D(g1)
2c(g2)=21=2=D(g2)
2c(g3)=22=4=D(g3)
2c(g4)=21=2=D(g4)
最后就可以得到著名的polay公式。
L=1|G|?∑1|G|mc(gi)
至于如何使用这个定理，我们只需要找到每个置换的循环节即可。

    推荐阅读


    上一篇：自定义view+属性动画实现

    下一篇：Retrofit2.5怎么做到网络请求的处理的（）