当前课程知识点:组合数学 >  小乒乓球的组合之旅 >  排列还是组合 >  排列还是组合

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

排列还是组合在线视频

排列还是组合

下一节:格路模型与组合恒等式

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

排列还是组合课程教案、知识点、字幕

这些歌曲大家很熟悉吧

是啊有的同学就会说了

黑板上的排列组合我是舍得解

就是未必能解开呀

确实是

其实在组合数学中

即便是非常简单的概念

排列组合也可以给你变幻出非常难的题目

那么今天呢我们就从基本的定义出发

带大家一起来回顾一下排列组合的定义

那么我们呢还是拿乒乓球为例吧

比如说我现在有4个乒乓球

我分别给它标上号

1号 2号 3号 4号

这时候我想要从4个乒乓球中选出3个

如果说我选的顺序我要一一记录下来的话

那么这样的方法就被称为排列

从4个球中选出3个进行排列的话

它实际上就是我们常说的P(4,3)

如果说我是选3个球出来

但是我把3个球呢放在一起

这时候3个球之间是没有顺序关系的

那么我们就做了一个组合

用什么来表示呢

如果从4个球中选出3个进行组合的话

我们实际上用的是C(4,3)

为了和后面的一般的题目相区别呢

我们这里面因为所有的球是不一样的

因此我们进行排列的时候会说

这叫做无重排列

而进行组合的时候它也被称为无重组合

如果用形式化的语言来进行描述

排列英文叫做Permutation

它意思说从n个不同的元素中

我要拿出r个来进行排列

它们之间是有顺序关系的

那么它的个数呢就被称为是排列的个数

一般我们就用P(n,r)来表示

当然有些书中也用A(n,r)来进行表示

注意这里面我们认为所有的元素

相互之间是不重复的

对于组合来说

组合的英文叫做Combination

它一样

也是从n个不同的元素中取出r个

与排列相区别的是它不考虑顺序

这时候我们(用...貌似多余了)

一般用C(n,r)来表示

从n个元素中取r个进行组合

有的呢也会把这个n和r的位置进行排列

比如说有的写的是C(n,r)

有的呢写的是Cnr(n为下标,r为上标)

当然这都是各个书的不同的排版形式

表示的都是同一个意思

对应于排列来说它的最基本模型

就是放球模型

也就是说我如果要从n个元素中

取r个的排列的典型模型

就是我要把n个不同的球拿出来

放到r个不同的盒子里面

而且要求每盒必须一个

那么对于这样一个排列数我应该怎么计算呢

我们来回顾这样一个放球的问题

我第一个球的时候

面对着一共有多少个选择呢

比如说第一个球我们现在

要从n个球中取出

那么它一共有n个不同的可能性

第一个球取出以后只剩下n-1个球

所以第二次再取的时候

只有n-1个可能性

一直到最后我取到第r步的时候

这个球只有n-r+1种可能性

根据乘法法则

我们一共走了r步

所以呢只要将n*(n-1)一直累乘到

n-r+1就是我们要计算的

排列数P(n,r)

那么我们用阶乘来表示的话

实际上P(n,r)等于n!除以

(n-r)!

对应着我们有的时候呢也会说

我们要把所有的数字n个球

全部进行排列

这时候就被称为全排列

我们一般用P(n,n)来表示

P(n,n)自然就等于n!了

我想这些概念大家都是很熟悉的

那么下面呢我们来讲解一下

对应于P(n,r)

所具有的递推关系

对于排列来说

相当于从n个球里面选择r个

放入r个盒子里

那么我们是否可以根据盒子

来进行分步递推呢

比如说我们先看第一个盒子再看第二个

直到最后一个盒子

那么对于第一个盒子

它有多少种可能性呢

其中我们会想第一个盒子

这时候从1到n这n个乒乓球(请忽略口误)

都是可以选择放在里面的

因此第一个盒子它的选择一共有n种

当第一个盒子的球已经尘埃落定之后

还剩下多少个球呢

剩下了n-1个球要放入到r-1个盒子里

这就相当于我们把规模减小了一点儿

要将n-1个球放入到r-1个盒子里

它的方案数就相当于是P(n-1,r-1)

通过分步的思路我们利用乘法法则

就得到了排列的第一个递推关系

也就是P(n,r)=nP(n-1,r-1)

除了分步之外我们还有分类的策略

那么分类来说的话

我们就不再看盒子了

我们可以去看球

用选不选第一个球作为分类

假如说我们不选第一个球的话

那意味着我们将还有剩下的

这n-1个球可以选择

这n-1个球最终要落到这r盒子中

因此它的方案数就应该是P(n-1,r)

而另一类中如果我选择了第一个球

第一个球是必选的

那么第一个球有多少种盒子可以来选择呢

它可以有r个盒子进行选择

而剩下的这一共有n-1个球

要放入r-1个盒子

因此选择第一个球的方案数

就应该是rP(n-1,r-1)

根据分类的思想我们就可以得到

P(n,r)等于P(n-1,r)

也就说不选第一个球的方案数

加上rP(n-1,r-1)

也就是选择第一个球的方案数

这将分类和分步的两个思路

定义了对应于

排列P(n,r)的两种不同的递推关系

刚才呢我们给大家介绍了有关排列的问题

对应于组合

其实它也有相应的放球模型

对于组合来说它和排列的区别

在于是否考虑顺序

而在排列的放球模型中它的顺序

是靠盒子上的标号来体现的

所以在组合中实际上它的盒子

因为不考虑顺序

因此是没有标号的

这时候它的放球模型还是说

n个不同的球

我要放入到r个相同的盒子中

也就是从n个球中取出r的组合模型

这时候我们就会发现

排列和组合其实密不可分

它们之间的区别无非就是盒子是否有标号

那么既然我们已经会算了P(n,r)排列数

那么C(n,r)该怎么来计算呢

我们就知道要想把所有的排列

又变成组合

只要把盒子上所有的标号去掉

就变成了组合

那盒子的标号一共有多少种呢

一共是r种标号的进行全排列

因此我们要消除多少个标号

意味着就要除以r的阶乘

我们知道P(n,r)等于n阶乘除以n-r阶乘

而P(n,r)=r!*C(n,r)

所以C(n,r)=n!/r!

乘以(n-r)!(貌似这样显示不太好,不过大家都能理解对吧)

组合数我们也算出来了

我们看一下组合具有什么样的性质

比如说我们看组合有这样一个式子

它说C(n,r)=C(n,n-r)

从这式子上看它说两个组合数是相等的

我们来仔细看一下

它的放球模型意义是什么

左边C(n,r)表示的是从n个球中取出r个

放到盒子里

那么我问你

取出来还剩多少呢

它是不是正好剩下了n-r个球呢

实际上也就是说左边对应的是取出的组合数

而右边对应的是剩下的组合数

自然它们是一一对应相等的

我们再看有下面一个性质

C(n,l)*C(l,r)=C(n,r)*C(n-r,l-r)

这个式子看似非常的复杂

怎么两个组合数乘在一起了呢

那么我们再仔细分析一下

它的组合意义是什么

它的左边是先从n个数中取出l个

第二步它再从l个数中取出r个

我们回头再想一想

当初在那个非文科班级中

他要选班委

是不是可以从n个人中选出l个班委呢

那么班委中我是不是还可以

再去选核心班委呢

那么我们在选出的L个班委中

再可以选出r个作为核心班委

那左边是不是就表示这样一个选举过程

那么回头我再想

我无非是要选出l个人

又从l个人中选出r个嘛

那我是不是可以先把核心班委指定了呢

那么看它的等式的右边

第一步C(n,r)

是不是可以理解说我先在n个人中

确定r个人作为核心班委

剩下的非核心班委

需要从多少人中选出来呢

那自然剩下n-r个人

其中它的非核心班委个数

只有l-r个席位了

因此我们可以看到

在这样等式的左边和等式的右边

实际上是不同的选举策略

但是选出的是同样的选举结果

自然这两个组合数相乘

乘积是一样的

所以我们看到

在这里我们介绍了排列的定义和组合的定义

下面呢我们会给大家讲述这些定义背后

具有的不同的含义

组合数学课程列表:

漫谈组合数学

-什么是组合数学

--什么是组合数学

--讨论题

-最精巧的排列——幻方

--幻方

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

-苦难的羊皮纸卷

--羊皮纸卷

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

-你的手机密码安全吗

--你的手机密码安全吗

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

-暴力枚举和抽象转换

--世界杯引出的问题

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

--一一对应

--七桥问题

--小结

--讨论题

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

-知识点串串烧

--知识点串串烧

期末测验

-期末测验--期末测验

排列还是组合笔记与讨论

也许你还感兴趣的课程:

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