当前课程知识点:组合数学 > 小乒乓球的组合之旅 > 排列还是组合 > 格路模型与组合恒等式
组合模型除了经典的放球模型之外
还有一个非常有趣的模型
它被称为是格路模型
我们来看这样一张图
实际上呢这张图实际上就是说
从0点一直走到右上角的一个点
这时候他走的时候不能走斜线
必须要么横着走要么竖着走
而且每次只能走一格
这就是格路模型
为什么说格路模型和组合是相关的呢
我们问大家这样一个问题
比如说我们要从左下角的(0,0)点
要走到(m,n)点
请问有多少种不同的走法
那么这时候我们就会想
如果每次都只能横着走或者竖着走
那意味着它可以表达成一个横竖横竖
不停交错的一个字符串呀
这意味着我们在所有的这些道路中
从(0,0)点走到(m,n)点
一共我要走多少步呢
水平方向上我应该走m步
垂直方向上我应该走n步
所以一共是m+n步
而在这所有的m+n步中
应该有多少个是水平方向的呢
它的位置在哪里呢
我们用这样一个串来表示
如果用X方向表示是水平走
Y方向用Y来表示
这时候它字符串相当于就是
XY XXYY依次下去
它的长度是m+n
其中它应该有m个X
那不就意味着在m+n这样中
我选择多少个位置做X呢
因此它对应的就是组合数
也就是从(0,0)点到(m,n)点
它的所有的格路数对应的就是组合数C
(m+n,n)
大家也许都知道
实际上我们都说组合实际上和杨辉三角
是有密不可分的关系
我们看这样一张图
我们会发现其实在每一个数字
它都对应的一个组合数
对应于第n行第r列
它的数值就是C(n,r)
而我们也知道
在杨辉三角中它的每一个数字
对应的也是a+b的n平方中间的某一项系数
那么是否对于一个二项式展开
a+b的n次方和组合
也有一定的关系呢
那么下面我们来看一下
有关二项式定理的内容
我们都知道根据二项式定理
我们有a+b的n次方
应该等于C(n,0)乘以a的n次方加上C(n,1)
a^(n-1)b一直累推过去
它的系数实际上就是一个组合数
那么为什么呢
我们来仔细分析一下
对应于a加b的n次方
就相当于有若干个a加b累乘在一起
这n个a加b最终呢
我们实际上在结果中会进行选择
比如说我在这样一个a或者b的结果里面
选择了a
而在第二个项中我选择了b
依此类推
对应于每一个展开式中的通项
a的n减r次方
b的r次方
它相当于在这n个括号中
一共在n个位置中选出了r个b
因此它的系数应该是C(n,r)
在二项式展开定理中我们就看到
a的n-r次方乘以b的r次方的系数就是C(n,r)
因此我们可以看到二项式定理和组合数
有一定的一一对应关系
那么我们再假设如果a和b的值都是1的话
代入上面的式子
我们就可以得到C(n,0)加上C(n,1)加上C(n,n)
就等于1加上1的n次方
也就是2的n次方
这是二项式定理的一个扩展形式
当然如果我们假设a等于1
b等于负1的话
我们同样会得到一个很有意思的公式
也就是C(n,0)减去C(n,1)一直加
累加或累减C(n,n)
最终由于它的左端项是0的n次方
因此它得零
对应不同的a和b
就会有不同的组合恒等式出现
这是一个非常有意思的事情
我们甚至可以去把a和b
分别用不同的自然数来替代
都会得到一些非常有意思的答案
在排列中我们给大家介绍了
有关排列的递推关系
实际上在组合中也有类似的递推关系
那么我们来看一下这样的杨辉三角
我们会发现杨辉三角有一个非常特别的性质
对应于中间的每一个点
都等于它上面的两个点之和
那是不是意味着组合也具有一定的性质呢
我们有这样一个恒等式
也就是说C(n,r)等于C(n-1,r)
加上C(n-1,r-1)
这样一个式子该如何证明呢
我们可以用格路来进行证明
比如说我们看到
格路问题对于等式的左边
C(n,r)我们可以设计它对应于从(0,0)点
一直到(n-r,r)点中
所有格路的数目
那么从(0,0)点一直到右端
它的所有的数目最后呢
可以根据最后一步是横还是竖分成两类
那么如果是横着走向的话
那意味着最后一个点自然就应该是(n-r-1,r)
如果是竖着走的
那么最后一个点应该是(n-r,r-1)
那意味着所有从(0,0)点到(n-r,
r)的格路数被分成了两类
一类是从(0,0)点走到这个点
也就是从(0,0)点走到(n-r-1,r)
另一类呢是从(0,0)点走到(n-r,n-1)
对应于这两类他们对应的所有的组合数
格路方案数就对应着等式右边的C(n-1,r)
以及C(n-1,r-1)
也就是C(n-1,r)和C(n-1,r-1)
因此我们可以发现
一些组合的恒等式我们可以用格路模型
给它一个非常漂亮的证明
那么下面呢我们再看一个
相对复杂一点的恒等式
这个恒等式似乎非常复杂
我们可以看到左边是C(m+n,r)
右边呢它不再是若干个组合数相加了
而是两个组合数相乘之和
这个式子被称为是范德蒙德恒等式
大家都知道范德蒙德实际上在数学界
还是非常有影响的
但是后来呢人们会发现
这个式子并不是范德蒙德独有的
实际上克努斯在他的书中曾经讲到过
这个式子实际上最早是在1303年
由我国的数学家朱世杰
在他的著作《四元玉鉴》中
就已经介绍给大家了
所以如果大家再看到这个等式的时候
应该称它是朱-范德蒙德恒等式了
介绍他的背景我们来看看
这样一个复杂的恒等式似乎无从下手
该怎么证明呢
那么我们来看左边它的含义是什么
C(m+n,r)
似乎我们要从m个加n个这么多个对象中
取出r个来
似乎我们已经把所有的对象分成两类
第一类有m个
第二类有n个
但是总共取出来了r个
那我们看看是不是可以
把它看成是红球和蓝球的抽取模型呢
比如说我一共有m个红球n个蓝球
中间我要取出r个
那不就对应的是等式的左边
对应来说我们现在这么直观的去看似乎很简单
是不是能够分步来求解呢
在我取出了所有的r个数中
我有可能一个红球都没有
有可能有一个红球两个红球三个红球
根据红球的不同数目
我们就可以把原来的
左边这样一个组合数分类来进行求解
那如果说只有一个红球的话
相当于我要在m个红球中先取出一个
剩下的(r-1)个球我要从蓝球中取出
那就相当于两个组合数相乘
也就是C(m,1)×C(n,r-1)
这不正是右边的某一项嘛
所以这道问题我们不需要进行一些推导
只需要对于放球模型进行合理的分类
就可以证明出左边的放球模型
和右边根据红球的个数进行放球模型
是等价的关系
因此可以看到
恒等式的证明其实花样繁多没有定法
对于组合来说
非常有魅力的学科就是去研究组合恒等式
实际上我们也可以看到
有一些书专门去研究组合恒等式
对应于简简单单的组合概念
有将近超过两百条的组合恒等式
大家都可以在其中发现各种
不同门类的证明方法
这是非常有趣的一件事情
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验