当前课程知识点:组合数学 >  组合之美 >  组合之美 >  组合之美之多样组合和全排列

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

组合之美之多样组合和全排列在线视频

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

下一节:组合之美之线性常系数递推关系

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

组合之美之多样组合和全排列课程教案、知识点、字幕

除了重排列之外

我们还咬文嚼字的介绍了

另外一个非常相似的概念

被称为是多重排列

那什么概念呢

可重

我们刚才说26个英文字母组成的

单词是可重排列

对应于每一个字母

随便选

多少个

任意

但是有可能有这样的情况

比如说我现在呢我要拿来三个苹果

四个梨

那这时候苹果的个数就是三个

梨的个数就是四个

这时候如果说对应于它的

每一个元素它的个数是有限制的话

我们称它为是多重排列

而在多重排列中

有一个非常典型的

也就是多重全排列

刚才说了

三个苹果四个梨

我全部拿来进行排列

这时候

就构成了一个多重全排列

多重全排列非常有用

我们呢

用另外一种形式来记录它

比如说

对应于从一共有N的元素中

对应于第一个元素

有r1个

第二个元素r2个依次向下

这时候它对应的多重全排列

可以就写成是

P(n;r1,r2,...,rl)

自然因为是全排列

所以所有的r加起来的和

就应该是等于n

那么一个典型的应用

实际上我们就在进行

多项式展开的时候

它的系数就是对应的一个

多重全排列

比如说我们对应的a1+a2

一直累加的n次方

那么我们知道

每一项如果展开的话

就是单独的a1+a2一直加到aL

那么一共有N个这么多个

取出来的时候就有可能

a1取了r1个

对应于我们要求它的系数

无非就是去计算一共是n个元素

其中a1有r1个

a2有r2个

对应的多重全排列

那么多重全排列的个数

该怎么计算呢

实际上我们首先想到

困难是什么

困难在于我们不知道对应的

有重复的元素该怎么处理

怎么办呢

一个很简单的办法

有重复不好

自然我们给的打上标号

彼此 就不重复了

最后呢要把它返回到重复的样子

它们进行不停的排列

无非 就是标号的阶乘

因此对应于一个多重全排列

实际上它的个数P(n;r1,r2,...,rl)

一直下去

就应该等于n!/(r1!r2!...)

依次累乘下去

这就是多重全排列的概念

刚才我们说到了可以有可重的排列

自然也会有可重的组合

那么可重的组合就意味着说

我可以从若干个元素中取出

r个,这里面的元素是

可以相同的

一个典型的例子就是说我

一共有n种水果

这里面我要把它拿出来

r个凑成一个果篮

注意这里面凑成一个

果篮里面是没有顺序的

因此这实际上就是一个可重组合

怎么来求解这个问题呢

我们用了一个非常巧妙的方法

也就是隔板法这意味着

我们现在应该把这r个

不同的水果分成多少个区域呢

因为它一共有n种

因此我要把它分成n个区域

我如果把它用隔板进行区分的话

需要多少个隔板能把整个

空间分成n个呢

实际上

只需要n-1个隔板

这n-1个隔板确定下来

剩下的无非就是把r个

元素往里面扔就好了

实际上它的答案

就是C(n+r-1,r)

就是对应于可重组合的答案

这个答案是非常奇妙的

隔板法也有很多的不同的应用

最重要的一个应用也就是来求解

x1+x2一直加到

XN等于r对应的

非负整数的个数

这里面它的答案就是一个对应的

隔板问题

它的答案就是C(n+r-1,r)

同样还有一个非常类似的东西

它的答案很相似

但是方法却不一样

也就是我们曾经介绍过的

对应的不相邻组合

我们有N个元素

我中间要取r个但是

要求每个元素取出来的序号

对应的是不相邻的

这个答案和刚才答案非常相似

我们当时用的是一种序数

对应的方法

它的答案正好是

C(n-r+1,r)和

我们的可重组合对应只是

符号上的不同

可以说我们用的八周的时间给

大家介绍的很多概念

都是和排列组合相关的

在这里面我们把相关的

概念总结成了一张表格

可以看到

我们基本上介绍了五种不同的

排列和组合

分别对应的是不同的状态和

不同的结果

但是实际上

对应于排列和组合

它里面内容博大精深

你可以从很多不同的角度去分析

甚至我们在后面会发现

我们甚至要用容斥原理、用鸽巢原理

处理一些对应的排列问题

和组合问题

对应于求排列和求组合的时候

大家算的最多的是什么

一定是这个感叹号吧

实际上

阶乘这个运算是非常复杂的

在我们说到的编程之美里面

有一章的题目就是不要被阶乘吓倒

为什么会这样说呢

因为阶乘的增长速率非常之快

而我们呢

也介绍了相应的一个方法

也就是说

如何把所有的阶乘对应的

全排列枚举出来

也就是我们下面要回顾的

全排列的生成方法

那么何为全排列生成算法呢

我们可以拿这些小球来看

比如说红球

蓝球

绿球

这时候呢我们这三个球来回的

不断的换它的顺序

实际上大家知道

就是三的阶乘个不同的全排列

那么这些全排列要

全部把它枚举出来

就是应用到了全排列的生成算法

我们给大家介绍了若干

过全排列的生成算法

包括用递归的方法、字典序的方法甚至呢

用SJT的算法

下面呢我们来回顾一下

字典序的基本概念

说到字典序

实际上我们就按照

ABCD的字典排序

对于全排列进行综合的演绎

我们会发现

比如说求83967521的

下一个排列

我们的思想是什么

首先对于字典序说

从末尾向左边有一个爬山 的过程

出现第一次下降的时候

就意味这个数字应该可以变大

那这时候我们依次从右向左

找到第一次下降的位置

在这道题目中刚好是

4这个位置是一个变化的位置

因此我们把4拿出来

4拿出来之后呢

必须要和它后面的数字进行交换

如果要和小的数字进行交换的话

自然这个数字就会变小了

我们要依次向下递增

因此4应该和它末尾后面的

比它稍微大一点的数字进行交换

进行交换

在这个例子中我们会发现

我们要找后者中比4大的

最小的那个数

正好是5

因此这里面我们把4和5进行交换

交换之后

产生了一个新的序列是

839657421

那么这时候我们会看

这里的后缀

7421并不是最小的一个后缀

我们只需把它后缀翻转

就可以变成一个最小的后缀

因此这时候我们就会说

839647521的下一个排列

应该是839651247

对应回顾字典序法

它无非就是经过了三个步骤去

依次求解下面的排列的是什么

而对应于SJT的算法

实际上用人的一种排列的思想

来模拟递归的方法比如说

求1234对应的全排列

对应的我们要去求的

实际上是要来计算每个数字

可以移动的方向

对于数字总是指向比它小的话

那么它就可以移动

在这里1234

我们首先对应了所有的数字的

方向都是向左移动的

那这是最大的这一个

就应该是4

4依次呢就要和3进行交换

交换之后

我们相当于每一步都要

先从小到大排列之后

方向都向左

作为初始的一个结果

第一步应当是选择当前的

最大可移动数

这里面所有的数字都是可以移动的

最大的一个就是4

而4作为可移动数要和

它相邻的数字进行交换

这时候正好4和3进行交换

4就和3进行了交换

生成了1243

接着呢

接着

4又和2进行交换

接着

又和1进行交换

交换之后发现

4已经达到了左端

没有办法再进行向左移动了

这时候我们实际上做了

一个很奇妙的事情

也就是说

这时候当4已经达到顶端

不能在移动的时候

我们要去找当前最大的可移动数

最大的可移动数在这个状态下

应该是3

3和2交换之后

比它大的数字将会 改变方向

因此32一交换

4的方向就变成向右了

4的方向指向1

比它小

因此4这时候又变成了

可移动的数字

依次往下就会生成一个新的排列

4和1交换变成1432

依次4再和3交换

依次4和2进行交换

接着依次往复

只要我们保证每次运算过程中

都在找移动数中最大的

那一个和它的相邻数进行交换

而且当这个数字移动之后

比它大的任何数字都要换方向

我们就可以完成了一个

全排列的生成算法

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

-漫谈组合数学--最精巧的排列——幻方

-苦难的羊皮纸卷

--羊皮纸卷

-苦难的羊皮纸卷--作业

-你的手机密码安全吗

--你的手机密码安全吗

-漫谈组合数学--你的手机密码安全吗

-暴力枚举和抽象转换

--世界杯引出的问题

--世界杯引出的问题--练习

--一一对应

--七桥问题

--小结

--讨论题

-大家谈组合数学(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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

组合之美之多样组合和全排列笔记与讨论

也许你还感兴趣的课程:

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