前言
昨天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定理不能解决带有颜色限制的染色问题的原因
zyqn好强啊!!!!!!!
I loved as much as you will receive carried out right here. The sketch is tasteful, your authored subject matter stylish. nonetheless, you command get got an nervousness over that you wish be delivering the following. unwell unquestionably come further formerly again as exactly the same nearly very often inside case you shield this hike.
198234 776922Can you give me some guidelines for piece of software writing? 432887
487060 28620wohh precisely what I was searching for, thankyou for putting up. 257219
950518 859536Hey there! Good stuff, please keep us posted when you post once again something like that! 587859
456786 964088Really properly written story. It will probably be helpful to every person who utilizes it, as well as myself. Keep up the great function – i will certainly read much more posts. 32224
608064 543229Its great as your other weblog posts : D, thanks for posting . 903556
508602 436113Some times its a pain in the ass to read what men and women wrote but this web internet site is quite user friendly ! . 502203
50953 699564I really like your writing style, great information, thankyou for posting : D. 229389
991225 522724Yay google is my king helped me to discover this great internet site ! . 531328
414945 417042i was just browsing along and came upon your weblog. just wantd to say wonderful web site and this post actually helped me. 339290
554286 708300Incredible! This blog looks just like my old one! Its on a entirely different topic but it has pretty much the same layout and design. Fantastic choice of colors! 169481
643719 469046A blog like yours need to be earning significantly funds from adsense..-., 224922
472174 722430I was reading some of your content on this site and I feel this internet website is truly informative! Maintain putting up. 279192
278417 582828Thank you for your really great details and feedback from you. san jose car dealers 694644
Glad to be one of several visitors on this amazing website : D.