当前课程知识点:组合数学 > 初识母函数 > 母函数是函数的母亲吗 > 母函数的定义(2)
所以我们说其实母函数呢
它只是有一个形式上的意义
就是一个形式幂级数
但是有人就会问了
为什么我们需要引入一个母函数呢
我们会发现其实在一开始
伯努利研究色子的时候
他遇到了一定的困难
在现实中我们也经常有这样的困难存在
就好比 请问同学们 尤其是男同学
早上起床的时候
如果要整理面容 刮胡子的话
会遇见什么问题呢
会发现没有镜子的话
似乎就不太容易去刮胡子了
那这个时候遇到这个困难
我们需要找一种映射的方式
来帮助大家解决问题
其实这种思想不止是在现实生活中
在我们的数学界也经常用到
我们可以回头看
对这样一个式子 大家觉得该怎么算呢
对于这样的幂次乘法直接运算是非常困难的
那么大家应该都记得
实际上我们给它找了一个对数的映射
将原来的幂次运算变成了简单的加乘关系
回头再通过幂次和对数之间的对应关系
直接找到了原问题的解
其实我们发现 在母函数中
同样是这样一个关系
我们会发现母函数一开始的时候
我们用两个色子来研究这个问题
发现直接计算是非常困难的
最终我们发现通过分步来考虑的时候
把多项式引入到这个问题里
随着多项式进行加乘运算求得系数以后
再对应回来
直接得到了答案
这也就是把困难问题经过一个映射关系
变简单的一个典型例子
那这时候我们再回头看
为什么需要引入母函数呢
我们发现其实母函数
蕴含的就是一种映射关系
那我们仔细分析一下
是什么样的映射关系让母函数
具备了计数的法则呢
所以我们可以看到
实际上在色子的投掷问题出现困难之后
我们不再进行直接的求解
而通过去对应它的多项式乘法 而求系数
转换成了求序列的问题
那么是如何能够实现这样一个对应关系呢
我们来分析一下
对应于多项式乘法
对于一般的多项式
我们都可以把它写成这样的形式
那么其中ak代表了x的k次方的系数
bk代表x的k次方在第二个多项式中的系数
把它们展开之后
我们去求对应的x的n次方的系数
实际上是在第一项中
取了x的i次方前面的系数ai
对应的要构成x的n次方
那么在第二项中
必然要找到对应于B n-i x n-i这一项
它们两个既然相乘之后
就得到了x的n次方的部分系数
也就是ai乘以b n-i
这实际上对应的就是乘法法则
也就是说n个计数对象
我们把它划分成了i个对象和n-i个对象
进行分步的处理
对于这里面i实际上是一个取值的分类
对于不同的i
实际上我们可以对应着不同的划分策略
因此对于不同的划分策略
我们i取0到n进行累加之后
就可以得到最终的计数结果
也就是相应的系数cn等于∑ai乘以b n-i
i从0到n
因此我们可以看到
虽然只是我们非常熟悉的多项式乘法
其中却蕴含了乘法法则和加法法则
正是这样的多项式的乘法运算
使得母函数具备了计数的能力
因此我们可以说
正是这样的母函数映射
才使原来的色子投掷问题的困难得到了解决
这时候我们再回头看这个多项式
我们应该叫它是什么呢
其实我们可以叫它是函数
也可以叫它是母函数
形式完全一样
就是一个长相
但是到底什么变了呢
我们会发现在函数中我们关注的
是自变量x和它的目标函数G(x)
而在母函数中
我们的落脚点就放到了系数上
同样一个东西仅仅是视角的改变
但是它们的功能和用途发生了巨大的变化
我们可以看这样一幅图
如果大家仔细看看
觉得这是一个什么图呢
这似乎就是个老太太嘛
但是如果我转一下呢
她变成了一位年轻的公主
所以它的结构没有发生变化
仅仅是视角发生了变化
就让我们产生了新的思维 新的想象力
那到底母函数是什么呢
其实有一位数学家叫做赫伯特·维尔夫
曾经用一句非常经典的话概括了
母函数是什么
他说母函数啊
就是一列用来展示一串数字序列的挂衣架
有了这样一个挂衣架
就能让我们有非常有效的计数方法
我们再回头来看
这样一个式子
这时候确实我们知道了
它既是一个函数也同时也是一个母函数
对应于函数和母函数
我们回顾一下它的发展历史
其实最早提出函数概念的
是在1694年莱布尼茨首先提出了函数的概念
经历了这么多年的发展
它已经成为了我们现实生活中
时时刻刻要用到
我们在高等数学中学习的
一个非常重要的概念
那么它的发展实际上缺不了
伯努利家族的贡献
1718年
伯努利终于给了它一个名字叫x的函数
而他的学生欧拉给函数给予了符号
那么在母函数 其实它的起步并不晚
同样是伯努利家族
在1705年开始研究色子的时候
已经有了初步的概念
但是经历了1740年欧拉的整数拆分之后
仍然没有具体的概念
直到100年之后
才有拉普拉斯提出了母函数的概念
可以看到函数和母函数其实起步的时间
是几乎同时的
可以说母函数并不是一个新的概念
那么我们来看这样一幅图
这样一看实际上大家觉得这是一个树根吧
盘枝错节的 如果我把它转过来
大家会发现这就是一棵树
而函数和母函数
正好像这样树根和树枝的关系一样
结构是一样的
同时它们都有一些雄厚深远的发展历史
但是现在来看
母函数在它的发展过程中
逐渐被人淡忘了
而直到计算机出现了
因为它计算太复杂了
只有当计算机出现之后
才会让它具有博闻和生机(貌似不太对,难道是勃勃生机不成)
同时呢我们会发现
它的方法逐渐又让计算机
具备了更多的计算能力
使得组合计数好像是计算机中的大脑一样
正所谓正看是根 逆是树
而古树新花 却让组合数学和计算机
有了进一步的结合
我们回顾一下母函数的定义的发展历史
会发现其实在1705年的时候
伯努利首先去研究了掷色子的问题
但是他并没有把它真正的形式化成某种形式
直到他的学生欧拉去研究了整数拆分数
虽然他已经给出了母函数形成的答案
但他仍然没有给出母函数的形式
直到100年之后
才有拉普拉斯把这个理论形式化
定义出了母函数这样的定义
所以我们可以看到
一个思想的发现并不是显而易见的
即便是我已经接触到它了
但也未必能够形成一个抽象的概念
最终还是由拉普拉斯总结了一百年之内
人们的工作
把母函数定义做成了这三行字
回头在看这三行字的背后
其实蕴含很多的思想
可以说我们和函数相比较
母函数和函数完全是不同的概念
不同的思维
它似函数 但是非函数
真正它是什么呢
它实际上是数学上非常有用的一种思想
就是映射
其实如果大家学了组合数学以后
会发现在很多地方
我们都要用到映射的思维
这种思维的引导下
能让我们去发现很多不一样的东西
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验