当前课程知识点:组合数学 > 小乒乓球的组合之旅 > 多样的组合 > 可重组合
我们已经知道了无重组合的概念
但是实际上在现实生活中
并不是所有的东西都不一样啊
比如说
我们今天想要做一个漂亮的果盘
那这里面我们可能有苹果
可能有橘子 可能有梨
那么我们可以说有这样一个问题
我们就是要拿4个
要么是梨 要么是橙子 有多少种可能性呢
这个问题就不再是我们刚才介绍的
无重组合了
这里面我们会发现
实际上这些元素是可以重复的
我可以有两个梨 可以有两个橙子
那对应于这样的梨和橙子
已经把元素进行了分类
由于它是可以重复的
我们称它为多重集
那么无重组合的定义已经不再适用了
因此我们给它一个新的名字
叫做可重组合
可重组合意思是说一共有n种不同分类的元素
我们要从中间取出r个
为了以示区别
无重组合我们直接用的是C(n,r)
但是在这里
因为是可重组合
我们在上面加一横杠
也就称为C bar (n,r)
那么怎么来计算可重组合呢
我们还是拿橙子和梨来看一看
我们可以看到
其实如果我们想要选择4个水果的话
我实际上对它进行了分类可以是橙子
可以是梨
如果要选择4个的话
我们就会发现
我们根据两个不同的分类
一边是橙子 一边是梨
对于这样相当于橙子是一个盒子
而梨是另外一个盒子
在不同的盒子里面
甚至有的盒子可以为空
所以我们发现
可重组合是需要一个新的模型的
所以为了方便起见呢
我们先不说水果了
我们还是拿一 二 三 四作为元素的代表
有这样一个问题
比如说元素的集合A
其中包含了一 二 三 四
四种不同的元素
其中我要取出5个进行可重组合
也就意味着我取出这5个元素中是允许重复的
那我应该怎么来表示呢
实际上我们来看
一 二 三 四分别可以做成一些盒子
那么如果我从元素中取出了两个一
我可以意味着从1号盒子中
我取出了两个球
那么如果有这样一个可重组合
5个元素 分别是1 1 3 3 4
因为是组合 顺序无关
因此我们把次序呢
按照一个递增的次序进行排列
对它进行表示
对应这样一个可重组合
1 1 3 3 4
该如何用放球的模型来表示呢
我们可以看到
一 二 三 四 4个盒子
1出现了两次 意味着从它里面取了两个球
而这两个球实际上是相同的
所以有一 二 三 四
下面对应着两个球 零个球
两个球 一个球
就对应了1 1 3 3 4这样一个可重组合
到此我们就会发现
可重组合照样也可以拿放球的模型来表示
它标志着是要取r个完全相同的球
放到n个有区别的盒子中
这时候有一个很奇妙的地方
每个盒子是允许放0个球或者1个球
甚至于多于一个球的
而在无重组合我们的模型是不一样的
在无重组合中我们说n个球是有区别的
而盒子是无区别的
并且我要求每个盒子必须要放一个球
不能多于也不能少于
那么同样如果是另外一个问题
我要拿4个球
中间我要有两个盒子对应着C(4,2)
意味着从一 二 三 四
这样四个不同的球中
我取出两个放到相同的盒子里
大家可以看到可重组合和无重组合
对应的是两个不同的放球模型
那么我们已经知道无重组合该怎么计算了
无非就是C(n,r)嘛
那怎么去计算可重组合呢
我们希望如果能够把可重组合
转换成我们知道的无重组合
似乎我们就可以解答了
那么下面我们看一下怎么来求解可重组合
所以我们要计算可重组合
主要的思路就是想要构造一个相关的无重组合
刚才我们拿这样一个可重组合的例子为例
研究了它的结构
那我们会看到它的序号对应于从0到4
我们如果把当前的数字和它的序号相累加
会产生一个新的序列
如果这个序列构造之后是一个无重组合的话
那我们就可以得到可重组合的计算公式
我们来看对于这样一个序列
它的最小值是多少呢
因为最小的一个数字
就应该是序列中最小的一个数字
因此是1
而在当前这样一个数字中
最大的数字可能是4
它的序号最大为5减1 4
因此它的最大方案数
最大的序列应该是4加上5减1
其中这就是它的所有数字的范围
那么它的范围从1到8
要选择5个数字
从无重组合的定义来看
这样一个构造出来的可重组合
应该和C(8,5)的数字是一一对应的
因此我们把它扩展一下
对应于一个可重组合a1 a2一直到ar
其中因为是个组合
我们将它从小到大进行排序
因此a1一直到ar是在1到n之间的若干个数值
它们的序号可以从0一直到r-1
根据刚才的思路
我们要将序号和数字相加
产生了一个新的序列
也就是a1 a2+1 a3+2一直累加到ar+r-1
我们同样要去看它的范围是多少
那么这r个数字中最小的一个数字
当然是从1开始的
那么最大的一个数字
它的数字ar的范围最大达到n
加上它的序号r-1
因此在这个序列中
最大的数字中就应该是ar加上r-1的最大范围
也就是n+r-1
那么这r个数字的取值范围
应该是从1一直到n+r-1
这就给我们一个思路
实际上在n个不同元素中取r个进行组合
允许重复的组合数就应该等于C(n+r-1,r)
但是我们回头看
我们是构造出来一个组合
那么它是不是无重的呢
也就是说在这样一个序列里面
会不会有某两个数字是会相等的呢
我们给予一个证明
首先我们想它是否有可重的
我们先假设确实是存在两个数字相等了
假设i小于j
ai加i-1 也就是构造出来这样一个位置
它的数值会和其他的某一个位置的数值相等
它等于aj加上j-1
我们看对应来说
ai和aj对应的序号是i和j
由于我们知道这样序列是一个递增的序列
因此i小于j就意味着ai应该小于aj
而ai小于aj i又小于j的话
那么这样的一个累加和不可能相等
因此我们发现通过它已知的条件
就产生了矛盾
那么必然
原来的假设是不存在的
也就意味着任意的两个数字
在这个序列中它们是不重复的
从而我们发现通过序号和累加序列
我们就构造出来了一个无重组合的模型
刚才呢 我们用累加序号的方法
证明了可重组合实际上就等于C(n+r-1,r)
那有没有一个更加直观的证法呢
我们下面用另外一种方法给出证明
其实我们回头再想
对应于梨 苹果 橘子
它无非就是把所有的元素分成不同的小格子了
那是不是我们也可以用隔板的方法
把所有的元素进行分类呢
有了这样的思想我们来看一下
实际上我们要从n个不同的元素中取出r个
意味着把r个这么多的元素
要分成n个区域
如果要分成n个区域的话
我们中间可以加隔板
隔板 n-1个隔板就构成了n个区域
因此我们这里面原来的问题就转化成了
把r个相同的元素用n-1个隔板
进行划分的问题
那么大家都知道
对于n-1个隔板
在所有的这个位置中进行选择
无非是所有的元素加上隔板
一共位置有n-1+r个
其中我要选出n-1个作为所有的门框隔板
剩下的r个位置放给元素就好了
这直接就告诉我们
我们实际上就是相当于
从n+r-1个元素中取出r个
就相当于原来的可重组合了
因此我们用了一个更加直接简便的方法
同样得到了可重组合方案数就应该是C(n+r-1,r)
这个问题可以进一步的扩展
我们可以看到原来
有多少个梨 多少个橘子
我们是不是可以拿变量来代替呢
比如说有这样一个问题
对应于线形方程组
x1+x2+...(一直加,加到)+xn=b
那我问你 这样一个线形方程组
它的非负整数解的个数是多少个呢
如果我们把原来的那些元素
全部都换成数字1的话
就相当于我应该把b个1分配到n个区域内
那这个问题和刚才的隔板模型是一模一样的
因此线性方程组整数解
同样可以用隔板的方法得到类似的答案
对应于x1加x2一直加到xn等于b
它的非负整数解个数就等于C(n+b-1,b)
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验