当前课程知识点:组合数学 >  小乒乓球的组合之旅 >  多样的组合 >  可重组合

返回《组合数学》慕课在线视频课程列表

可重组合在线视频

可重组合

下一节:不相邻组合

返回《组合数学》慕课在线视频列表

可重组合课程教案、知识点、字幕

我们已经知道了无重组合的概念

但是实际上在现实生活中

并不是所有的东西都不一样啊

比如说

我们今天想要做一个漂亮的果盘

那这里面我们可能有苹果

可能有橘子 可能有梨

那么我们可以说有这样一个问题

我们就是要拿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算法

--程序支持与Stirling公式

-第二周作业

--H

--U

--G

--思考题

--公式测试

--作业讨论区说明

-第二周演示程序

--程序讨论区说明

--排列数和组合数的计算

--全排列生成

--组合生成器

--共享程序

-参考资料:Stirling估计式

--Stirling估计式

初识母函数

-母函数是函数的母亲吗

--母函数的定义(1)

--母函数的定义(1)--练习

--母函数的定义(2)

--母函数的定义(2)--练习

-母函数的简单应用

--母函数的简单应用(1)

--母函数的简单应用(2)

--初识母函数--母函数的简单应用

-整数拆分

--整数拆分(1)

--整数拆分(2)

-Ferrers图像

--Ferrers图像

--Ferrers图像--作业

-母函数与递推关系

--母函数能做什么

--Hanoi问题(1)

--Hanoi问题(2)

--偶数个5怎样算

--偶数个5怎样算(2)

--母函数小结

-大家谈组合数学(2)

--科研,找工作与组合数学

-第三周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第三周演示程序

--程序讨论区说明

--整数拆分

--汉诺塔

--共享程序说明

线性常系数递推关系

-Fibonacci数列

--Fibonacci兔子

--Fibonacci恒等式

--线性常系数递推关系--Fibonacci数列

-Fibonacci数列的应用

--桌布魔术

--桌布魔术--练习

--Fibonacci的直接表达式

--Fibonacci优选法

--艾略特波浪曲线

-线性常系数齐次递推关系

--定义

--特征多项式

--母函数与特征多项式

--根据特征多项式求解递推关系通解(1)

--根据特征多项式求解递推关系通解(2)

--线性常系数递推关系--线性常系数齐次递推关系

-说“数”解题

--说“数”解题(1)

--说“数”解题(2)

-第四周作业

--H

--U

--G

--GT思考题

--作业讨论区说明

-第四周演示程序

--程序讨论区说明

--Fibonacci优选法

--Fibonacci数值计算

--程序共享说明

-爆笑花絮

--爆笑花絮

-参考资料:K线分析中的Fibonacci 相关理论

--Fibonacci retracement资料

神奇的序列

-Catalan数

--计算机界的精灵

--Catalan数的直接表达式

--Catalan数的各种实例

--神奇的序列--Catalan数

-指数型母函数

--指数型母函数

--指数型母函数的应用

--神奇的序列--指数型母函数

-错排

--错排1

--错排2

--神奇的序列--错排

-Stirling数

--第一类Stirling数

--神奇的序列--Stirling数

--第二类Stirling数

-母函数小结

--母函数小结

-大家谈组合数学(3)

--采访郭家宝(BYVoid)

-第五周作业

--H

--U

--G

--思考题

--作业讨论区说明

-第五周演示程序

--讨论区说明

--Catalan数

--第二类Stirling数

--程序共享

容斥原理和鸽巢原理

-且容且斥

--容斥原理

--容斥原理的证明

--容斥原理和鸽巢原理--且容且斥

-容斥原理的精妙

--容斥原理的应用(1)

--容斥原理的应用(2)

--容斥原理的应用(3)

-回忆过去,容斥新解

--容斥原理的应用(4)

--容斥原理的应用(5)

--容斥原理的应用(6)

--容斥原理和鸽巢原理--回忆过去,容斥新解

-鸽子抢巢

--鸽巢原理

--鸽巢原理--练习

--鸽巢原理的应用(1)

--鸽巢原理的应用(1)--练习

-看得见摸得着的鸽巢

--鸽巢原理的应用(2)

--韩信点兵

--中国剩余定理

--容斥原理和鸽巢原理--看得见摸得着的鸽巢

-6人行和Ramsey数

--6人行

--Ramsey数

--小结

-第六周作业

--H

--U

--G

--GT

--作业讨论区说明

-第六周演示程序

--讨论区说明

--Find a multiple

--程序共享说明

-可以转的世界

--可以转的世界

--可以转的世界--练习

--伽罗华与群

--群的定义

--群的定义--练习

--群的一些概念

-置换群

--置换群

--群--置换群

--共轭类

--对换

--对换--练习

--置换群的应用

-Burnside引理

--着色问题的等价类

--Burnside引理--作业

--Burnside引理

--Burnside引理的应用

-闲话群

--无处不在的群(1)

--无处不在的群(2)

-第七周作业

--H

--U

--G

--作业讨论区说明

Polya定理

-Burnside引理的困境

--Burnside引理的困境(1)

--Burnside引理的困境(2)

-从Burnside到Polya

--Polya定理

--Polya定理的应用(1)

--Polya定理的应用(2)

-立方体旋转

--立方体旋转(1)

--立方体旋转(2)

--立方体旋转--作业

--立方体旋转(3)

--立方体旋转--作业

--立方体旋转(4)

-母函数型Polya定理

--母函数型Polya定理(1)

--母函数型Polya定理(2)

--母函数型Polya定理(3)

--母函数型Polya定理(4)

--Polya定理--母函数型Polya定理

-图的计数

--图的计数

-总结

--本章小结

-第八周作业

--H

--U

--G

--GT

--作业讨论区说明

-大家谈组合数学(4)

--采访黄连生老师

组合之美

-组合之美

--组合之美之计数

--组合之美之排列组合

--组合之美之多样组合和全排列

-组合之美之线性常系数递推关系

--组合之美之线性常系数递推关系

-组合之美之多样的序列

--组合之美之多样的序列

-组合之美之鸽巢原理

--组合之美之鸽巢原理

-组合之美之转动群与染色

--组合之美之转动群与染色

-采访邹欣

--采访邹欣1

--采访邹欣2

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

可重组合笔记与讨论

也许你还感兴趣的课程:

© 柠檬大学-慕课导航 课程版权归原始院校所有,
本网站仅通过互联网进行慕课课程索引,不提供在线课程学习和视频,请同学们点击报名到课程提供网站进行学习。