【转】Polya定理
2024-10-12 00:36:13
转自:http://endlesscount.blog.163.com/blog/static/82119787201221324524202/
Polya定理
首先记Sn为有前n个正整数组成的集合,G为Sn的置换群,C为Sn的着色集。那么我们等于是要求C中有多少种着色方案是不等价的。定义两种着色等价的概念:如果对于在C中的两种着色c1、c2,存在置换f使得f*c1=c2,那么c1和c2就是等价的。要想求不等价着色的个数,我们要先证明一个定理,即:
Burnside定理:设G(c)={f|f属于G,f*c=c},C(f)={c|c属于C,f*c=c}。那么对于每一种着色c,那么与c等价的着色数=|G|/|G(c)|。
证明:首先可以证明G(c)为Sn的一个置换群。那么对于任意的f*c=g*c,可知f的逆*g属于G(c),所以g={f&h|h属于G(c)}。那么在|g|=|G(c)|。所以与c等价的着色数=|G|/|G(c)|。这样我们就得到了Burnside定理。
我们现在就用Burnside定理来得到最终的答案。先设N(G,C)为C中不等价的着色数。我们考虑这样一个计数过程:求所有的(f,c)满足f*c=c的总对数。那么我们有:
sum{|G(c)|}(对于每一个c属于C)=sum{|C(f)|}(对于每一个f属于G)。
由Burnside定理可对等式左边进行替换,得到:
sum{|G|/与c等价的着色数}(对于每一个c属于C)=sum{|C(f)|}(对于每一个f属于G)。
如果我们把右边的式子展开的话,等价类相互合并和就把分母给消去了,最后得到的就是不等价类的个数:
N(G,C)*|G|=sum{|C(f)|}(对于每一个f属于G)。
这个公式就是Polya定理。即:N(G,C)=1/|G|*sum{|C(f)|}(对于每一个f属于G)。那么对于任意的带变换的着色计数问题,我们都可以把变换用置换群表示出来,然后对于每一个置换群考虑其|C(f)|的个数,这可以通过递推、DP、或者是矩阵快速幂来解决。
最新文章
- Linux编译工具:gcc入门
- (四)G1 garbage collector
- Bar菜单
- 【BZOJ1208】宠物收养所(平衡树,splay)
- class 函数
- spring + myBatis 常见错误:@Autowired注解失败
- FFMpeg 滤镜中英文对照
- 怎么让alert弹出框的内容可以换行?
- HDU2196computer(树上最远距离 + DP)
- Web service project中导入的库JAX-RS(Java EE 6.0新产品)
- addChildViewController相关api深入剖析
- T-SQL利用Case When Then多条件判断
- Oracle 流式制造功能培训
- winform窗体——布局方式
- Windows下动态库的隐式调用
- Android(java)学习笔记220:开发一个多界面的应用程序之界面间数据传递
- 实现Android操作系统11种传感器介绍
- find 路径必须在表达式之前
- 异常处理第三讲,SEH(结构化异常处理),异常展开问题
- 基于Java的Arc Engine二次开发的环境的配置
热门文章
- 解决 odoo.py: error: option --addons-path: The addons-path 'local-addons/' does not seem to a be a valid Addons Directory!
- Java常用的技术网站
- 等差数列(bzoj 3357)
- python爬虫成长之路(二):抓取代理IP并多线程验证
- 3.2 配置构建Angular应用——简单的笔记存储应用
- Oracle数据库操作分类DDL、DML、DCL、TCL类别清单异同
- [Tool]Inno Setup创建软件安装程序。
- MachineKey 操作 之 应用集群中SSO应用生成MachineKey
- nodejs持续学习--必须关注4网站
- View动画和属性动画