对Pólya原理及其应用的小结

群的定义(性质)

一个群应满足一下四种性质:

a)封闭性:$\forall a,b\in G,\exists c\in G,s.t.a*b=c.$

b)结合律:$\forall a,b,c\in G,(ab)c=a(bc).$

c)单位元:$\exists e\in G,\forall a\in G,ae=ea=a,则称e为单位元。$

d)逆元:$\forall a\in G,\exists b\in G,ab=ba=e,则称b为a的逆元,记b=a^-1.$

置换群

置换:n个元素1,2…n中每个数被a1,a2…an取代,其中ai互不相同且都属于1,2…n。

置换群:置换群包含这n个元素所有的置换。记作G,|G|为置换的个数,下同。

$Z_k$(K不动置换类):置换群中能使元素k不动的置换的全体为$Z_k$

$E_k$(等价类):元素K在置换群中所有元素的分别作用下能变化到的位置的全体。

|E_k|*|Z_k|=|G|

Burnside引理

研究每个元素在各个置换下不变的次数的总和:用D($a_i$)表示在$a_i$置换下没有变动的元素的个数。

这一段有点烦且没什么用我就不详细写了。Brunside引理主要就是说|G|个置换所能到达的不同状态数

使用burnside引理,总的时间复杂度为O(nsp)。(n表示元素个数,s表示置换个数,p表示格子数)如此之高的时间复杂度不能为我们所接受,因此我们需要寻找一种更简便快速的算法。

polya

循环节数:网上都有

设G是p个对象的一个置换群,用m种颜色涂染p个对象,则不同染色方案为:

其中G={g1,g2…gs},c(g1)为置换gi的循环节数

(那篇论文里就这么点)

(溜了溜了)