当前课程知识点:组合数学 > 组合之美 > 组合之美 > 组合之美之排列组合
我们有了加法法则和乘法法则之后
我们会发现
我们有一个非常有用的概念
也就是排列和组合
这实际上是组合数学中
最最基础 而且最最常用的概念
大家一说起来
排列实际上它的概念 是什么
比如说我从N个学生中间
要选出r个进行排队
那这个时候我们会发现
我们选出的r个人
是有顺序 的
而另外一个概念组合
组合的概念是说
我从N个学生中找出
r个组成 一组
在组中实际上是没有顺序 的
那这就揭示了组合和
排列之间的关系
也就是一个是有序的
而一个是无序的
那么它们的公式有什么关系呢
实际上我们在想
在组合中拿出的那
r个人
我如果拿过来
对它进行r!排队的话
这时候它不就变成了
所有的排列了吗
实际上排列和组合之间的
差距无法就是它的排队方案数
对应着
如果说P(n,r)也就是从
N从取r 个
进行排队的方案数等于N的
阶乘除以(n-r)!的话
那么
对应的组合C(n,r)实际上
只是在P(n,r)的结果上
再除以r!就可以了
刚才我们说到了可以从
若干个同学中取出若干个
进行排队或者组合
但实际上组合有另外一个
非常有用的模型
也就是我们曾经介绍过的
格路模型是什么意思呢
对应于我们有这样一个X
正方向和Y的正方向对应的区域
每一个单位代表一个格子
这时候如果我要从左下角
一直走到右上角(m,n)点的话
这时候有一个要求
每次必须走X方向的正方向一格
或者是Y方向上的正方向一格
不允许回退
那这时候请问
从(0,0)点沿着格路走到
(m,n)点有多少种不同的可能性呢
对应于我们在课程中曾经介绍过
这是组合的一个典型模型
它的方案数就是相当于我
在一共M加N这么多步中
取出M步作为X方向的
因此它的答案就是C(m+n,m)
当然它也等于C(m+n,n)
我们有了排列
有了组合
我们就可以做出各种各样的题型
实际上对于排列来说
刚才是说从N个不同的学生中
取出r个人来
自然这r个人
都是不一样的
但是
如果我是从若干个苹果
若干个梨中
取出r个水果呢
实际上
这里面就会有可重元素
因此我们还有另外一个问题
被称为是可重排列
同样呢
我们还有多重排列
多重全排列
还有呢
我们对应于组合来说
也对应着有可能有元素的重复
也有可能出现的
甚至不是在一个线上进行排列
有可能就是圆排列
那么下面我们介绍一下圆排列
对应于P(n,r)我们都很熟悉
就是r个人拿出来站队
站成了一条线的样子
但是对于圆排列呢
圆排列实际上
我们是想说
对应于一个圆的上面若干个位置
它进行排列有多少种不同的可能性
这时候我们会说
我们并不知道圆排列
该如何去做
但是
线排列我们是知道的
有没有可能我们直接把
圆排列转化成线排列呢
对于一个圆我们实际上只要
把它一剪刀剪开的话
就变成一个线排列
对应于一个圆排列
它如果上面有
r个元素的话
实际上我们会发现
它有多个位置
把它变成不同的线排列
也就是对应于一个圆排列
它有可能产生若干个线排列
而如果是r个元素
在这个排列上
它能产生多少个不同的
剪刀的位置呢
正好是r个因此
圆排列的个数就应该等于
对应的线排列个数P(n,r)
再除以一个剪刀可能的
位置数r就可以得到
圆排列的方案数了
刚才说到的所有的排列
元素都是不相同的
当然其实现实中很多情况下
元素都是有可能相同的
这就被称为是可重排列
举个简单的例子
我们都知道
英文字母吧
一共有26个
那么
我们要在英文字母26个中
随意的拿过来进行排列的话
请问四个字母构成的单词
一共有多少个呢
实际上
每一位都有26个选择
每一位都是可以重复的
因此这是一个典型的
可重排列的方案
对应于如果我们一共有
N个元素可以选择
要给它r个位置的话
那么
它的可重排列方案数就
应该是n的r次方
对应于26个字母构成四个的
单词实际上就是每一个
位置上都有26个选择
一共选四次
因此是26的四次方
现在把这个题目稍微改一下
同样还是从26个英文字母中
我要选择四个
但这时候要求
每个字母彼此之间都要不相同
那意味着
这实际上构成了一个排列
而且是不能重复元素进行的排列
那就是我们最一开始
介绍的P(n,r)的概念
也就是从26个元素中取出四个
进行无重的排列
也就是P(26,4)
当然这道题目
还可以进一步的扩展
这道题目我们改成这样
还是从26个字母中选出4个来
而且还要求每个字母都不相同
但是呢
我们知道
英文字母都有一定的规则
比如说
我要求b和d不能相邻
那你能凑成多少个这样的
四位的英文字母吗
实际上大家会想
直接去看不相邻的实际上很难
那是不是我能够抛掉
b和d相邻 的呢
那我就可以说首先我不管
b和d相不相邻
所有的方案就应该是P(26,4)
对应于b和d必然 相邻 的
四位的一个单词怎么去计算呢
既然b和d相邻
那意味着b和d都会选出来的
那剩下还有几位置呢
四个里面
用掉了两个
那还有两个位置空缺
所以
要从24个字母中
选出两个来
也就是C(24,2)这时候BD相邻
它们合在了一起
另外两个元素和这合成的
元素一共是三个元素
所以三个元素进行全排列是
三的阶乘
而bd相邻有可能是bd
有可能是db
因此还要再乘以二
因此答案就是P(26,4)
减去C(24,2)
乘以3!再乘以二
-什么是组合数学
--什么是组合数学
--讨论题
-最精巧的排列——幻方
--幻方
-漫谈组合数学--最精巧的排列——幻方
-苦难的羊皮纸卷
--羊皮纸卷
-苦难的羊皮纸卷--作业
-你的手机密码安全吗
-漫谈组合数学--你的手机密码安全吗
-暴力枚举和抽象转换
--世界杯引出的问题
--世界杯引出的问题--练习
--一一对应
--七桥问题
--小结
--讨论题
-大家谈组合数学(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
-知识点串串烧
--知识点串串烧
-期末测验--期末测验