前言
昨天hht来给窝萌增长了姿势水平
hht真的好神啊!伏地膜!
问:“你搞OI时如何平衡高考与竞赛”
hht:“我不用学习也能考很好,我在高一的时候已经把高中内容看完了”
正文
hht主要讲了Burnside引理的不完全证明和用Burnside引理推出Pólya定理
下面主要围绕这两方面来讨论
Burnside引理的不完全证明
有一个前置结论hht没有证明,说是需要引入很多无关的概念:
$|Z_k| \cdot |E_k| = |G|$
其中$|E_k|$表示一个等价类的大小,$|Z_k|$表示作用在这个等价类上使等价类不变的置换的数量
这个引理的证明似乎要用到群里边的轨道?我们可以参见这里:https://en.wikipedia.org/wiki/Group_action#Orbits_and_stabilizers
以下的内容建立在我们认为这个引理是正确的基础上
我们先来看一看Burnside引理的形式:$N = \frac{1}{|G|} \sum\limits_{g \in G}{\chi (g)}$
那么我们只需要证明:$N \cdot |G| = \sum\limits_{g \in G}{\chi (g)}$
对于$\sum\limits_{g \in G}{\chi (g)}$,我们实际上是先枚举置换,再枚举染色情况,再看是不是一个不动点
我们考虑换一个枚举顺序,我们枚举所有的染色情况,然后看有多少置换可以使这个染色情况成为不动点
那么这不就是$|Z_k| \cdot |E_k|$吗?于是$N \cdot |G| = \sum{|Z_k| \cdot |E_k|} = N \cdot G$,得证
使用Burnside引理推导Pólya定理
我们还是考虑枚举置换
如果一个置换可以使一种染色情况成为不动点
那么这个置换的每一个循环节只能被染成同一种颜色
所以每一种置换$g$我们有$k^{m(g)}$种染色方案($k$为可用的颜色数,$m(g)$为置换$g$的循环节)
于是我们就不用枚举所有的染色情况了,可以直接用$k^{m(g)}$计算
于是Pólya定理的公式就变成了$N = \frac{1}{|G|} \sum\limits_{g \in G}{k^{m(f)}}$
这个证明过程也非常直观地给出了Pólya定理不能解决带有颜色限制的染色问题的原因