burnside引理与Polya定理计数法
Text
我们将一个集合到它自身的一个一一映射称为一个置换
对于集合[1,2,3,4]
就是一个置换,把1换成3,2换成4,3换成2,4换成1
我们也可以将其写成循环节的乘积的形式
因为1到3,3到4,4到1这是一个循环节
2自己构成一个循环节
以一个例子来引入burnside引理
这是百科上的图片
其中一个状态就是集合里的一个元素
定义置换群为置换的集合
通过置换群中的变换操作后可以相等的元素属于同一个等价类
burnside引理就是等价类的个数等于每种置换长度为1的循环节个数之和除以置换的种类数
设这个置换群为
即等价类的个数
好吧我并不会证。。
如何用它来解决问题?
回到上面的例子,共有16个状态,集合大小为16
置换有4种,不动、顺时针90度、转180度、逆时针90度
需要求等价类的个数
列出来并写成循环节的形式
不动:a1=(1)(2)…(16)
逆时针转90度 :a2=(1)(2)(3 4 5 6)(7 8 9 10) (11 12)(13 14 15 16)
顺时针转90度 :a3=(1)(2)(6 5 4 3)(10 9 8 7)(11 12)(16 15 14 13)
转180度:a4=(1)(2)(3 5)(4 6)(7 9)(8 10)(11)(12) (13 15)(14 16)
总的等价类个数就是
下面介绍Polya定理
如果我们需要用m种颜色对n个点染色,染色并且经过置换本质不同的染色方案数(例如对正方体染色)
理论上可以用burnside引理求解,此处介绍更加方便的Polya定理
设
染色方案