当前课程知识点:组合数学 > 小乒乓球的组合之旅 > 排列还是组合 > 排列还是组合
这些歌曲大家很熟悉吧
是啊有的同学就会说了
黑板上的排列组合我是舍得解
就是未必能解开呀
确实是
其实在组合数学中
即便是非常简单的概念
排列组合也可以给你变幻出非常难的题目
那么今天呢我们就从基本的定义出发
带大家一起来回顾一下排列组合的定义
那么我们呢还是拿乒乓球为例吧
比如说我现在有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算法
-第二周作业
--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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验