当前课程知识点:组合数学 >  Polya定理 >  从Burnside到Polya >  Polya定理

返回《组合数学》慕课在线视频课程列表

Polya定理在线视频

Polya定理

下一节:Polya定理的应用(1)

返回《组合数学》慕课在线视频列表

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算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

Polya定理笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。