当前课程知识点:组合数学 > 神奇的序列 > 母函数小结 > 母函数小结
下面我们来总结一下
其实这两三周的课基本上就围绕了
一个主题
也就是母函数
什么是母函数呢
拉普拉斯就用三句话告诉了我们
什么是母函数
无非就是一个多项式
而我们关心地是多项式里面的序列
这时候这就被为母函数
因为母函数主要是蕴含了系数序列
虽然概念非常简单
它实际上用途也被称为无非就是
一个数字序列的挂衣架嘛
但是它却给我们带来了
很多不同的应用
其中最重要的一个就是
线性常系数齐次递推关系的求解
如果我们已经有了一个
线性常系数齐次递推关系
我们直接就可以写它的特征多项式
根据求特征多项式不同的根的情况
比如说有重根
有无重实数根和共轭复根
根据这两种不同的情况
我们分别去待定系数
设立它的通项表达
而根据它始值
我们就可以很容易地联立方程组
计算出来所有的通项表达式
所以可以知道母函数这种方法
虽然好象只是简单的函数的样子
但是它却经过了一定的抽象之后
帮大家解决了几乎所有的
线性常系数齐次递推关系
而除此之外
我们还把母函数这三行字
又变换了一下
不仅仅是说用x的k次方
作为通项目了
我们为了求排列
我们还引出了一个用xk次方
除以k的阶乘作为通项的
一个母函数
一个称为普通型母函数
另外一个称为是指数性母函数
而这两个母函数用途不同
普通型的母函数呢
主要面向的就是求组合
而指数性母函数一看到排列
首先就应该想到是指数性母函数
而在传统的普通型母函数中
我们常用的就是1减ax分之一
因为它的系数就是a的k次方
而对应于指数性母函数
我们常用的是e的x次方的展开式
大家对这个知识一定要了然如行
最后我们还给大家介绍了
不仅仅是线性常系数递推关系
我们还给大家介绍了一些
神奇的序列
这些序列有特殊的递推关系
甚至有的还不是线性的了
但是它可以帮助大家
去解决很多的问题
还有一个非常有意思的问题
其实一直贯穿我们组合数学的始终
最开始的时候
从第一章我就给大家介绍
排列组合我们就是用的
小乒乓球放盒子来给大家介绍
到现在学习了
我们会发现同样一个问题
n个球放到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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验