置换群 Burnside引理 Pólya定理(Polya)
置换群
设\(N\)表示组合方案集合。如用两种颜色染四个格子,则\(N=\{\{0,0,0,0\},\{0,0,0,1\},\{0,0,1,0\},...,\{1,1,1,1\}\}\),\(|N|=2^4\)。
对于\(N\)上的所有置换,它们组成的群称为置换群,记为\(G\)。\(G\)中任意两个置换的积仍在\(G\)中。
Burnside引理
又称轨道计数定理、Burnside计数定理、Cauchy-Frobenius定理、Pólya-Burnside引理。
定理描述为:\(等价类数量=\frac{\sum c_1(g_i)}{|G|}\)。其中\(c_1()\)即不动点数。
正方形顶点二着色
用两种颜色染正方形的四个顶点,求等价类数量。
共有四种置换,分别为转0°、90°、180°、270°。其不动点数为16、2、4、2,因此答案为6。
圆排列
将n个不同东西放在环上,求等价类数量。
共有n种置换,\(g_i\)是转了i/n圈的置换。
\(|N|=n!\)。由于\(c_1(g_n)=n!\),而\(c_1(g_i)=0(i<n)\),答案为\(\frac{n!}{n}=(n-1)!\)。
n截棍染色
一根棍子分成\(n(2|n)\)截,用m种颜色染色,相邻两截不能染同色,求等价类数量。
先求\(N\)。同bzoj1008,\(|N|=m(m-1)^{n-1}\)。
有不变和翻转两种置换。答案为\(\frac{1}{2}m(m-1)^{n-1}\)。
Pólya定理
颜色很多的时候,Burnside引理就十分麻烦。因此有Pólya定理。
定理描述为:设\(H\)是对原来所有被染色对象的置换群,而不是对\(N\)的置换群。设颜色有m种,则染色方案数为\(\frac{m^{c(h_i)}}{|H|}\)。其中c()为循环节数。
正方形顶点二着色
四种循环分别为\((1)(2)(3)(4),(1,4,3,2),(1,3)(2,4),(1,2,3,4)\),因此答案为\((2^4+2^1+2^2+2^1)\div4=6\)。
Pólya定理与生成函数
bzoj没一道题……
那就不讲了
最新文章
- Python基础篇【第2篇】: Python自定义函数
- HAST 使用笔记
- hdu 1018:Big Number(水题)
- Spring IoC反转控制的快速入门
- 使用radioGroup的时候,每个radioButton的状态选择器要使用 state_checked=";";属性,不能使用selected
- UVALive 3959 Rectangular Polygons (排序贪心)
- [Jquery] jQuery.cookie帮助类 (转载)
- Oracle 10g数据库概述
- SQL查询重复记录
- Noip2016组合数(数论)
- 自动化测试用例getText()获取某一个元素的值返回null或空
- form 组件
- Hive学习01-基础常见问题
- Codeforces 982E Billiard 扩展欧几里德
- win7 64位安装opencv3.0
- 维护贴--linux下 mysql数据库的备份和还原 (转)
- Java队列Queue
- Android ScrollView嵌套ScrollView滚动的问题解决办法
- 正向工程configuration配置连接
- Python学习-40.Python中的迭代