当前课程知识点:组合数学 > 初识母函数 > 母函数是函数的母亲吗 > 母函数的定义(1)
你知道什么是母函数吗
知道 母函数是函数的妈妈
那你知道是什么是函数吗
函数是母函数的宝宝
如果用色子来说 你知道什么是母函数吗
那就是好几个色子合在一起是母函数吧
对呀 那你喜欢母函数还是喜欢函数啊
母函数
为什么呀
因为母函数比函数要长得大
哦 真好
说起函数 大家肯定特别的熟悉
因为我们学函数学了很多很多年了
那么我们来看这样一个式子
这是一个非常长的多项式
一般我们叫它什么呢
我们叫G(x)就是一个函数
那么今天呢我们学什么呢
我们今天学的名字和函数非常相似
叫做母函数
那么大家都会想
什么是母函数呢
我们不如打开教材看一下
我们翻到第二章 定义2.1是这样描述的
它说对于一个序列c0 c1 c2
我们构造一个函数G(x)
等于c0加上c1x加c2x平方 一直累加下去
称G(x)为序列c0 c1 c2的母函数
从这个概念上来看
我们发现母函数是什么呢
不也就是一个多项式吗
我们看到的它说到的是有一个序列
这个序列作为函数的系数
称这个函数就是序列的母函数
这么一比较
怎么母函数和函数长得是一模一样呢
那么到底有什么区别呢
母函数到底还是不是函数呀
我们又看书上有这样一句话
它说组合数学主要是要计数
用的最多的工具是母函数
函数我们用来干什么的
函数我们用来求极值
我们用来求x自变量的取值范围
我们要分析的它的收敛性
但是在组合数学中
我们用母函数是用来计数的
那么我们又觉得这到底是怎么一回事儿呢
回头我们又查了一下百度和维基百科
它们上面都说到组合数学中的母函数
就是计数的重要工具
尤其它在概率论和计数中是一种重要的方法
说到这儿我们更加的糊涂了
到底这个母函数是用来做什么呢
我们不如拿一个例子来看一看
今天呢 我们用色子的投掷
给大家讲什么是母函数
我们来研究一下
如果我投掷两粒色子
最后两个色子加起来的总和是六点
能有多少种可能性呢
那实际上就相当于第一个色子
和第二个色子加起来和值等于六
那么我们现在所知道的计数方法
无非就是基本的乘法法则和加法法则
它对应的就是分类的思想和分步的思想
在这里我们也是一样
比如说我是不是可以分步来看呢
第一个色子能有多少种可能性呢
第一个色子它甩出来的时候
一二三四五 只有五种可能性
那么一旦第一个色子确定了
因为两个色子之和是确定的六
所以呢 第二个色子随之也确定了
因此第一个色子有五种方法
第二个色子只有一种方法
五乘以一等于五
这自然说我原来掷出六点
只可能有五种可能性
另外我还可以分类来看啊
比如说它有可能是一加上五
有可能是五加上一
有可能是二加四 四加二
有可能两个还都是三
那么每一种方法我们累加起来
发现它就一共是五种
这个问题虽然很简单
用到的也是最最基本的乘法法则和加法法则
但是我们如果色子有这么多呢
大家觉得该怎么去计算呢
难道还要挨个挨个去枚举吗
其实啊 在三百年前伯努利就已经研究了
这么多色子的问题
他当时问如果我投掷m粒色子出去
加起来点数总和等于n的所有可能方式
有多少种
我想同学们在这里面似乎就有点茫然了
该怎么做呢
我们现在研究是相对简单的一个例子
只有两个色子
那么只有两个色子如果掷出n点的话
有多少种可能性呢
我们就相当于把整数n
拆分成两个自然数之和
这时候由于n的存在
我们再进行枚举的话
相对来说就比较复杂了
我们只能一个色子一个色子来看
这时候先看第一个色子
它能出现多少个点呢
一点两点三点四点五点六点
它们之间是或的关系
那么在或的关系里面
我们会发现 或 实际上对应的是加法
那应该把什么东西加到一起呢
我们如果把点数直接相加的话
那么它直接就累加了
并不能实现两个色子的累加过程
我们在逐个分析一个色子
对于这一个色子我们可以看到
它如果有两个点的话
也可以看作一个分步的策略
先添一个点 再添一个点
这时候有相当于有两个点进行相乘
也可以表示成点的平方
当然点的平方我们并不习惯
我们可以用x平方来表示
如果这个两个点是x平方
那么四个点就可以是x四次方
第一个色子x平方
第二个x四次方
它们之间投掷是分步的过程
因此合并之后就得到了一个x六次方
这时候我们发现
实际上对应于x的k次方进行相乘
它就可以表示出来色子的投掷过程
因此用指数可以对应点数
因此这时候我们就可以用x加x平方
一直加到x六次方这样一个多项式
来代表一个色子的投掷过程
同样对于第二个色子也有类似的一个式子
第一个色子第二个色子
分步的策略我们就可以用乘法
用两个多项式相乘来代表色子的投掷
这时候我们要去求x的六次方
前面的系数实际上就是代表了
有多少种出现了有六点的方式
比如说 对于第一个色子一个点
第二个色子五个点
实际上我们就得到了x一次方乘以x五次方
对应的这样一个系数
同样两点四点三点三点四点两点五点一点
这样一个枚举过程
实际上就是我们在做多项式乘法
而它得到的系数
就是对应能够得到六点的系数
也就是方案数
那么对于这样一个多项式乘法
把它转化成一个函数形式
就相当于G(x)等于x加x平方
一直加x六次方的平方
展开式中它们的系数就代表了
x的n次方的系数就是两个色子
掷出n点的可能方法数
从这里面我们就会发现
实际上系数起了关键的作用
它可以在函数的运算中对应计数的序列
通过刚才的分析我们知道了
每一粒色子都可以用一个多项式来表示
那么对于伯努利问题中m粒色子呢
我们自然可以拿多项式累乘就可以得到
因此对于投掷m粒色子的时候
它可以用G(x)等于x加x平方加x三次方
一直加到x的六次方的m次方来表示
那么伯努利想要知道
加起来的点数总和等于n有多少种方式
那就意味着我们想求这个G(x)里面
x的n次方前面的系数
走到这里我们会发现
确实这是一个函数
这是一个多项式
但是呢 我们并不关心这个多项式的值
我们现在关心的却是它的系数了
所以可能看到母函数确实是一位母亲
但是谁是孩子呢
计数的序列作为函数的系数就是它的孩子
所以母函数的定义是这样的
首先我们应该关注每一个计数序列
而每一个计数序列对应的是x的k次方
这时候我们把它累加起来
就构成了一个函数
这个函数和传统的函数意义不同
因为我们关注的是它的系数
因此这就是母函数的定义
那么母函数的定义是谁提出的呢
实际上是拉普拉斯在他研究概率的时候
研究了母函数的方法和有关的定义
回头我们看 实际上母函数是为了干什么呢
它和函数有什么区别
首先母函数它是用来计数的
传统的函数我们要考虑x的取值范围
而在这里x取值是什么
我们并不关心
同时 原来的函数中我们要考虑它是否收敛呀
它是否有极值
在这里面x似乎就是一个占位置的地方
我们根本不在乎它取什么
也不在乎G(x)最终能够达到多少数值
所以我们会看到
虽然这形式上仍然是一个函数的样子
但是母函数似函数非函数
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验