当前课程知识点:组合数学 > Polya定理 > 母函数型Polya定理 > 母函数型Polya定理(2)
下面我们来拿
等边三角形的着色举例
比如说等边三角形的三个顶点
我们现在可以给它
进行红蓝绿的三着色
请问有多少种不同的方案
刚才我们已经计算过了
那么我们现在想更细致化
比如说我想问你
对应的三个珠子都是
红色都多少种方案
两个红一个绿多少种方案
一红一绿一蓝多少个方案呢
我们就利用母函数的方案来求解
对于它的置换群其实很简单
无非就是旋转正负120度
以及对它的对称轴进行翻转
以及不动
一共有6个不同的置换
依次列在这里
我们必须要找相应的
母函数的形式
我们看第一个
三阶循环有一个 这时候
它对应的母函数意味着
括号内的三个应该全部都取同色
那它的母函数就是R的3次方
加B的3次方
加G的3次方
而同样对于一阶循环一个
二阶循环一个
这样的形式它写出来就是
R加B加G乘以R平方
加B平方加G平方
一阶循环三个
这样实际上就是
R加B加G的3次方
我们如果把这样的
式子全部联立在一起
去求若干项前面的系数
就是对应的方案数
比如说我们想问全部都是
红色珠子有多少种
那就是求展开式中
R的3次方前面的系数
那么R的3次方大家看一下
在哪些项目中是可以的呢
比如说第一行中R加B加G
这个里面发现有一个
R的3次方
而前面因为有两个
所以2乘以对应的系数就可以了
下面这一项
R加B加G乘以R平方
加B平方加G平方
实际上它也会产生R的3次方
一共有多少个这样的置换
3个
对于下面的R加B加G的3
次方同样也有R的3次方
我们把这些所有累加在一起
发现正好是2个加3个加1个
同时不要忘记
对应的波利亚定理中
我们还要除以
置换的个数
置换的个数是6
所以刚好算出来是
2加3加1除以6等于1
意味着在三角形的
顶点上全部取红色
只有一种方案
同样还可以算别的
比如说要RGB它的系数有多少
当然我们不需要
把所有的式子展开
我们只要看每一项就可以
第一项里面
对应的应该是R的3次方
加B的3次方
加G的3次方
这里面根本就不可能
有RGB存在
我们再看第二项
第二项里面每一项至少是平方项
因为它前面是R加B加G
后面是R平方加B
平分加G平方
因此也不可能出现RGB
这样依次累乘
只有最后一项
R加B加G的三次方里面
有可能有RGB项
而它有多少项呢
实际上我们都知道
就应该是3的阶乘
除以R有多少阶乘
G一阶乘
这样一个可重排列
同样不要忘记除以阶乘个数6
答案仍然是我们
对应的RGB有多少种可能性
答案仍然是1
同样我还可以算两个红珠子
一个蓝色珠子
也是一样
对于第一项
所有项都是三次幂
因此不可能存在R平方B
只有在第二项中我们
可以第一项取B
第二项取R平方
产生了一个
而一共有三种不同的置换
因此对于在第二行中
有两个对应的R平方B出现
对于R加上B加上G的三次方
我们同样可以求R平方B的系数
实际上也就是
可重排列出来的结果
可以认为是用三阶乘除以
R平方对应的
两个R的可重排列
除以2的阶乘再除以1的阶乘
同样再除以6就得到
对应的答案
我们再看一下
如果是四颗珠子
要镶嵌在正六面体上
有多少种不同的方案呢
我们再仔细想一想
正六面体应该有多少个顶点
大家会想正六面体
应该有8个顶点
现在我的提议是说我
只有4颗珠子
4颗红色珠子要镶嵌
在8个顶点上
这就是说有些点是空的
虽然都是一种颜色
但是对应的是镶嵌
红珠子和不镶嵌红珠子
这两种对应的二着色问题
这时间我们直接对于正六面体中
顶点进行二着色
进行计算就可以了
但是它要求求什么
最后的方案中
红色的珠子必须是四个
如果我们用R来表示红色珠子
用B表示不存在珠子的话
实际上我们就去求R的四次方
B的四次方
前面的系数是多少
这时候我们还是同样应用
母函数型的波利亚定理
首先我们应该把正六面体对应的
所有置换全部列出来
分析一下在不动的情况下
顶点置换应该是8个顶点
每个顶点都是一阶循环
因此是一阶级循环的8次方
对于面心面心
上面四个顶点和下面四个顶点
进行交换
所以四阶循环有两个
依次往下
我们都可以把顶点的
置换群全部列出来
我们要求的是R的
四次方 B的四次方
我们看第一项里有没有
R的四次方
B的四次方
第一项如果要将它写成母函数型
应该是一阶循环有八个
意味着母函数是
B加R的8次方
B加R的8次方自然会
存在一个B四次方 R四次方
它对应前面系数就应该是
从八项目里面取四个
也就是C(8,4)
对于面心对面心旋转
它的格式是四阶循环有两个
那写成母函数就是B的四次方
加上R的四次方的平方项
这里仍然会有对应的B四次方
R四次方
同样依次往下
每一项每一项都去分析
它是否存在B四次方
R的四次方
我们写出对应的母函数形式
就可以分析出对应的展开式中
B的四次方
R的四次方的系数
就应该等于C(8,4)
加上12
再加上9乘以C(4,2)
再加上八乘以C(2,1)
乘以C(2,1)
同样不要忘记还要
再除以所有的置换个数
对于正六面体
它的置换个数正好是24
因此累加之后除以24
答案就得7
什么意思呢
意味着在这样的
正六面体中如果四个顶点有珠子
而其他四个顶点没有珠子
的情况下
不同的方案应该只有7种
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验