当前课程知识点:组合数学 > Polya定理 > 从Burnside到Polya > Polya定理
我们这时候回头来看
刚才在伯恩塞德引理中
遇到了困难
也就是对于结构更为复杂
而且着色方案数非常多的情况下
我们发现直接去看对应的
着色图象集是非常困难的
有没有可能我们直接
看着色对象的结构呢
比如说我们无非就是在
这个六面体里面进行旋转
那么它的结构我们
是可以分析清楚的
无非就是它可以转可以翻
沿着对角线轴进行翻转等等
那么在这些翻转和
旋转的角度下
它是否产生了一定的变化呢
我们直接拿它对应的
着色对象来看
当然在立方体的世界中
大家觉得转起来有点晕
我们还是回到平面的结构
来看正方形顶点着色
正方形顶点着色的时候
我们在介绍置换群曾经说过
对于一个顶点
我给它打上标号之后
照样可以构造出置换群
比如说对于1 2 3 4
如果我们旋转90度的话
实际上就变成了4 1 2 3
这时候我就写成一个置换形式
而且这个置换是可以
写成循环结构的
意味着我们其实没有
必要去找对应的图象集合了
是不是可以直接去看
对应的顶点构造呢
我们来对比一下
其实在刚才说到
伯恩塞得引理的时候
我们把所有16个
图象全部都拿出来了
现在我们先不看这16个图象
我们直接看对应的
1 2 3 4四个顶点
如果我对它进行转动操作的话
它会发生什么样的变化
产生什么样的置换群呢
我们来看
对应于第一个角度
首先在0度的时候
它就是不变的
1点 2点
3点 4点仍然是它自己
那另外转90度会发生
什么样的情况呢
如果我转了90度的话
会发现它从1 2 3 4
变成了4 3 2 1
那这个时候
直接写成循环结构就是
4 3 2 1这样一个循环结构
当然我可以说对于180度
1和3对换
2和4对换
接着对于270度同样是四阶循环
对于这样的结构
我们想一想
循环内部表示什么
循环内部表示我一旦
发生变化以后
我这个位置将要
到达下一个位置
比如说在这里
对应于1和3互换
意味着如果旋转180度
1就会变成3
3就会变成1
那我们在伯恩塞德引理要找什么
要找的是说
转了以后还没有变的东西
那既然是1和3发生变化
如果1和3着的是同样颜色呢
比如说都是红色的
那我再转它两个点还是红色的
不会发生任何的变化
因此这里面我发现玄妙的地方
也就是对应于同一个括号内
在每个循环内部如果我们给它
着的方案颜色是一样的意味着
我在这个预算下
它的颜色方案是不会发生变化的
我们直接让循环来考虑怎么去
产生对应的不动图象
那我们来分析一下
假如说对应第一个伯恩塞德引理中
我们图象集对应的置换用G来表示
在下面的分析中我们考虑结构
这时候我们用G bar来表示
在每一个对应的G bar置换中
每一个循环内部要着同样颜色
这里既然只有红蓝
两种颜色选择
那意味着每一个
括号内就有两种选择
那一共有多少不同的
就意味着我应该用
2的k次幂来表示
k表示这个置换中
有多少个括号
有多少个循环
我们分析一下
对应于不动循环 不动的话
意味着一共有4个不动的循环
每个循环内部可以有
两种不同的选择
做出来就是2的4次方
而对应于如果旋转90度
只有一个循环
意味着4 3 2 1
他们必须要着同样的颜色
这时候只有两种选择
而对应于转180度
1换3 2换4
这时候1 3着同色两种选择
2 4着同色两种选择
总体我一共会有2的
平方次4种选择
270度也是一样
我们通过这样的分析找到了
在什么情况下有多少种可能性
我保证在这个运算下不会
对原来的图象发生变化
这是什么概念
这不就是我们说的
置换中的不动点吗
回头再看
在伯恩塞德引理中
恰巧c1(ai)对应的正好是我们
刚才列出的2的k次方的结果
那意味着冥冥之中我们实际上
不需要考虑所有的着色图案
我们应该考虑的是
对应的着色对象的结构
我们就会发现我们不需要再去
找对应图象群中的一阶循环了
我们要找什么
我们要找的应该是
对应于结构的置换群中
它的循环的个数
循环个数我们用C来表示
对应PI_bar我们这样的置换它的
循环个数就用C(PI bar)来表示
根据刚才的分析我们发现了
其实对于有多少个循环和
用m个颜色去着色的话
它的不动点个数是
m的C(pi bar)次方
而且我们知道对应于
原来在伯恩塞德引理中
它的c1(ai)就应该等于
m的P1 bar次方
这时候我们就发现
伯恩塞德引理可以完全改写了
这就是新产生的波利亚定理
在波利亚定理中有这样的概念
为了区分刚才对应
图象集置换我们采用了
G bar来对于结构的置换群
它分别包含了P1 bar,P2 bar
一直到对应的Pg bar
因为他们对应的都是
相同的循环或者置换
因为对于G和G bar来说
他们所有的置换个数是相等的
不同点在于这里面我们对应的
伯恩塞德引理是
对应的是所有图象集
而在波利亚定理中
对应的实际上是结构对应置换
而同时因为我们知道
我们在结构置换群中
考虑的是
对应每个置换有多少个循环
用C表示循环个数
这时候伯恩塞德引理
就改变成了要求等价类个数l
l就等于对应于一共m种颜色
给这么多个循环进行着色
因此所有的不动个数是
m的CPI bar次方
把对应的所有置换构成这样的
m次方加在一起之后
再除以对应的置换个数就是
我们要求的等价类个数
因此我们可以看到C1(ai)已经
完全变成了m的
对应的CPI bar次方
那么回头分析一下
我们发现波利亚定理和
伯恩塞德引理相比较而言
他们处理的对象是
着眼点不同的
波利亚定理处理的是结构
而伯恩塞德引理是
在图象集上进行操作
因此伯恩塞德引理往往会
由于图象集过于
复杂而面临巨大的困难
那么波利亚定理在此时
就起到了很大的作用
当然他们之间实际上是有桥梁的
所谓的桥梁就是对应
图象置换中的一阶循环个数和
对应于结构表达的循环进行
m种颜色着色
他们的个数是相等的
这也就把原来复杂的
问题转化成了
更为直观的波利亚定理
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(1)
--采访武永卫老师
-第一周作业
--作业说明
--H
--U
--G
--作业讨论区说明
-第一周演示程序
--程序讨论区说明
--幻方生成器
--换方计数
--屏幕解锁方案数
--欧拉路计数
--共享程序
-加减乘除来计数
--计数的基本法则
-排列还是组合
--排列还是组合
--小乒乓球的组合之旅--排列还是组合
-各种各样的排列
--圆排列和项链排列
--圆排列和项链排列--习题
--多重排列
--多重排列--练习
-多样的组合
--可重组合
--不相邻组合
--小乒乓球的组合之旅--多样的组合
-钟声里的全排列
--钟声里的全排列
--钟声里的全排列
--字典序法
--SJT算法
-第二周作业
--H
--U
--G
--思考题
--公式测试
--作业讨论区说明
-第二周演示程序
--程序讨论区说明
--全排列生成
--组合生成器
--共享程序
-参考资料:Stirling估计式
-母函数是函数的母亲吗
--母函数的定义(1)--练习
--母函数的定义(2)--练习
-母函数的简单应用
--初识母函数--母函数的简单应用
-整数拆分
--整数拆分(1)
--整数拆分(2)
-Ferrers图像
--Ferrers图像--作业
-母函数与递推关系
--母函数能做什么
--偶数个5怎样算
--母函数小结
-大家谈组合数学(2)
-第三周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第三周演示程序
--程序讨论区说明
--整数拆分
--汉诺塔
--共享程序说明
-Fibonacci数列
--线性常系数递推关系--Fibonacci数列
-Fibonacci数列的应用
--桌布魔术
--桌布魔术--练习
--艾略特波浪曲线
-线性常系数齐次递推关系
--定义
--特征多项式
--线性常系数递推关系--线性常系数齐次递推关系
-说“数”解题
-第四周作业
--H
--U
--G
--GT思考题
--作业讨论区说明
-第四周演示程序
--程序讨论区说明
--程序共享说明
-爆笑花絮
--爆笑花絮
-参考资料:K线分析中的Fibonacci 相关理论
-Catalan数
--计算机界的精灵
--神奇的序列--Catalan数
-指数型母函数
--指数型母函数
--神奇的序列--指数型母函数
-错排
--错排1
--错排2
--神奇的序列--错排
-Stirling数
--神奇的序列--Stirling数
-母函数小结
--母函数小结
-大家谈组合数学(3)
-第五周作业
--H
--U
--G
--思考题
--作业讨论区说明
-第五周演示程序
--讨论区说明
--Catalan数
--程序共享
-且容且斥
--容斥原理
--容斥原理的证明
--容斥原理和鸽巢原理--且容且斥
-容斥原理的精妙
-回忆过去,容斥新解
--容斥原理和鸽巢原理--回忆过去,容斥新解
-鸽子抢巢
--鸽巢原理
--鸽巢原理--练习
--鸽巢原理的应用(1)--练习
-看得见摸得着的鸽巢
--韩信点兵
--中国剩余定理
--容斥原理和鸽巢原理--看得见摸得着的鸽巢
-6人行和Ramsey数
--6人行
--Ramsey数
--小结
-第六周作业
--H
--U
--G
--GT
--作业讨论区说明
-第六周演示程序
--讨论区说明
--程序共享说明
-可以转的世界
--可以转的世界
--可以转的世界--练习
--伽罗华与群
--群的定义
--群的定义--练习
--群的一些概念
-置换群
--置换群
--群--置换群
--共轭类
--对换
--对换--练习
--置换群的应用
-Burnside引理
--着色问题的等价类
--Burnside引理--作业
-闲话群
-第七周作业
--H
--U
--G
--作业讨论区说明
-Burnside引理的困境
-从Burnside到Polya
--Polya定理
-立方体旋转
--立方体旋转(1)
--立方体旋转(2)
--立方体旋转--作业
--立方体旋转(3)
--立方体旋转--作业
--立方体旋转(4)
-母函数型Polya定理
--Polya定理--母函数型Polya定理
-图的计数
--图的计数
-总结
--本章小结
-第八周作业
--H
--U
--G
--GT
--作业讨论区说明
-大家谈组合数学(4)
--采访黄连生老师
-组合之美
--组合之美之计数
-组合之美之线性常系数递推关系
-组合之美之多样的序列
-组合之美之鸽巢原理
-组合之美之转动群与染色
-采访邹欣
--采访邹欣1
--采访邹欣2
-知识点串串烧
--知识点串串烧
-期末测验--期末测验