The whole world is my footage…

...

正在装标签云和树形的分类目录...

我不确定标签云对这个站的未来会有多大帮助,不过我真的很喜欢那个会旋转的标签云,从第一在infi那里见到它,我就知道自己已经爱上了这个,用字体的大小代表数量的众寡,用字体的深浅代表它们被访问的多少,而这两个都是用自己可以直观的事物去重现我们的数字...而这个会根据鼠标的位置向力道相反的方向旋转的水晶球一样的东西则更是美丽了~^ ^

...

ゆっくり読んでください ...

【专题】Polya 计数定理

References:

Polya 定理再小结
组合数学 原书第 5 版
除数函数的渐近上界? by vfleaking

。。统计在某个置换群作用下。。计算不等价的着色方案数的问题。。。
。。可以通过 Burnside 定理。。转化为枚举每一个置换。。。统计在该置换作用下等价的着色方案数的问题。。
。。而 Polya 定理则是巧妙的利用同一循环内着色必须相同这个事实,进一步简化后者的计算。。。

——————

习题:
http://acm.hust.edu.cn/vjudge/contest/view.action?cid=2823#overview

Burnside 定理:

的置换群,而 中对 封闭的着色集合。
中非等价着色数 由下式给出:

Polya 定理:

是集合 的置换。假如我们用 种颜色对 着色,则对 不变的着色数与 的循环数 有关:

。。。

——————

证明:

引理 1:

对于每一种着色 的稳定核 是置换群,而且对 中的任意置换
当且仅当 属于

推论 2:

中的一种着色,那么与 等价的着色数等于 中置换个数,除以 的稳定核中置换的个数。

Burnside 定理:

。。考察。。所有满足 的二元组 。。双计数。。
枚举 f 。。得到 。。(通过置换 不变的着色几何)
枚举 c 。。得到 。。(c 关于置换群 的稳定核)
根据推论 2 有:


(因为每个非等价着色对左式的贡献为 1。)

ゆっくり読んでください ...